数据结构期末考卷13.doc

数据结构期末考卷13_…__…__…__…__…__…__…__…__…_：…名…姓…… __…__…__…__…__…__…__…_：…号线..学… _…__…__…__…__…__…__ 订.__…__…：…级…班… …__…__装_..__…__…__…__…__…__…__…__…：…业…专… _…__…__…__…__…__…__…：…级…年……诚信应考 考出水平 考出风格 浙江大学城市学院 2013 — 2014 学年第 一 学期期末考试试卷 《 数据结构基础 》 开课单位： 计算分院 ；考试形式：闭卷；考试时间： 2014 年 1 月 14 日； 所需时间： 120 分钟 题序 一 二 三 四 五 六 总 分 得分 评卷人 得分 一．选择题 (本大题共 18 题，每题 1 分，共 18 分) 1. 数据的 包括集合、线性结构、树形结构和图形结构四种基本类型 A. 存储结构 B. 逻辑结构 C. 基本运算 D. 算法描述 2. 中任何两个结点之间都没有逻辑关系 A. 树形结构 B. 集合 C. 图形结构 D. 线性结构 3. 下面的程序段违反了算法的 原则。

void fun() { int x=2; while (!(x%2)) x=x*2; printf(“%d”,x); } A. 健壮性 B. 确定性 C. 可行性 D. 有穷性 4. 算法分析的两个主要方面是 A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 第 1 页 共 6 页 5. 用数组表示线性表的优点是 A. 便于插入和删除操作 B. 便于随机存取 C. 可以动态地分配存储空间 D. 不需要占用一片相邻的存储空间 6. 循环链表的主要优点是 A. 节约存储空间 B. 已知某个结点的位置后，能够很容易找到它的直接前驱 C. 在进行插入、删除运算时，能更好的保证链表不断开 D. 从表中的任意结点出发都能访问到任何一个结点 7. 可以用带表头附加结点的链表表示线性表，也可以用不带头结点的链表表示线性表，前者最主要的好处是 A. 可以加快对表的遍历 B. 节省存储空间 C. 使空表和非空表的处理统一 D. 可以提高存取表元素的速度 8. 在头指针为h且表长大于1的单向循环链表中，指针p指向表中的某个结点，若p->next->next==h，则 。

A. p指向头结点 B. p指向尾结点 C. *p的直接后继是头结点 D. *p的直接后继是尾结点 9. 线性表中，只有直接前驱而无后继的元素是 A. 首元素 B. 尾元素 C. 中间元素 D. 全部元素 10. 以下不是栈的基本运算的是 A. 删除栈顶元素 B. 删除栈底元素 C. 判断栈是否为空 D. 将栈置为空栈 11. 若用一个大小为6的数组来实现循环队列，且当前rear和fornt的值分别为1和4从当前队列中删除一个元素，再加入两个元素后，rear和front的值分别为 A. 3和5 B. 2和0 C. 0和2 D. 5和3 12. 最不适合用作链队的链表是_____ A. 只带队头指针的非循环双链表 B. 只带队头指针的循环双链表 C. 只带队尾指针的循环双链表 D. 只带队尾指针的循环单链表 13. 最不适合用作栈的链表是 A. 只有表头指针没有表尾指针的循环双链表 B. 只有表尾指针没有表头指针的循环双链表 C. 只有表尾指针没有表头指针的循环单链表 D. 只有表头指针没有表尾指针的循环单链表 14. 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程效率 。

A. 高 B. 低 C. 相同 D. 无法确定 第 2 页 共 6 页 15. 设n和m为一棵二叉树上的两个结点，中序遍历时，n在m后的条件是 A. n在m的右子树上 B. n是m祖先 C. n在m的左子树上 D. n是m子孙 16. 已知一棵普通树的广义表表示为a(b, c(e(h, i, j), f), d(g))，则此树的深度为 A. 2 B. 3 C. 4 D. 5 17. G是一个非连通无向图，共有21条边，则该图至少有___________个顶点 A. 7 B. 8 C. 9 D. 23 18. 用邻接表存储图，所用的空间大小___________ A. 与图的顶点数和边数都有关 B. 只与图的边数有关 C. 只与图的顶点数有关 D. 与边数的平方有关 二．填空题 (本大题共 10 题，每题 2 分，共 20 分) 1. 数据结构主要研究三方面的内容：数据的逻辑结构、 2. 计算机算法指的是解决问题的有限运算序列，它必具备输入、输出、有穷性和 这五个特性 3. 下列算法的时间复杂度为 得分 int test(int n) { int s=1; while(snext; q->next=p; p=q; q=r; } h=p; } 第 4 页 共 6 页 2．已知线性表中的元素按值递增有序排列，阅读下列程序，说明算法的功能： typedef struct { ElemType *list; int size; int MaxSize; }SeqList; void f2(SeqList &L, ElemType m, ElemType n) { int i=0, j; while(idata==x ) return BT->parent; p=t1(BT->left, x); if (p!=NULL) return p; p=t1( ② ); if (p!=NULL) return ③ ; return NULL; } 第 5 页 共 6 页 2. 下列算法是由无向图的邻接表生成邻接矩阵，请在空白处填入适当的语句，使该算法完整。

typedef struct Node { int adjvex; struct Node *next; } edgenode; //边结点 typedef edgenode *adjlist[ MaxVertexNum ]; //邻接表存储结构 typedef int adjmatrix[MaxVertexNum][MaxVertexNum]; //邻接矩阵存储结构 void t2(adjlist GL, adjmatrix GA, int n) { //由GL建立GA，n是图的顶点数 int i, j; edgenode *p; for ( i = 0 ; i adjvex ; ⑥ ; p = p->next; } } } 六．程序设计题 (本大题共 2 题，每题 10 分，共 20 分) 得分 1. 设链式队列用只带队头指针的循环双向链表表示，如下图所示: front 要求： ① 写出该链式队列的结点结构定义（即循环双向链表的结点结构定义）； ② 写出在该循环双链链式队列上进行入队列操作的算法（函数） 2. 设以二叉链表方式存储二叉树BT，要求： ① 写出二叉链表的结点结构定义； ② 写一算法（函数），由二叉树BT生成一棵新的二叉树，该新二叉树是将BT各结点的左右孩子交换后生成的（即BT任一结点的左孩子在新二叉树中是右孩子，右孩子是新二叉树的左孩子），要求返回新生成的二叉树根结点的地址（注意：原二叉树BT需保持不变）。

第 6 页 共 6 页 5 / 5。