当前位置:首页 >> 数学 >>

数据结构试卷(二)及答案

数据结构试卷(二)
一、选择题(24 分) 1.下面关于线性表的叙述错误的是( ) 。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 2.设哈夫曼树中的叶子结点总数为 m,若用二叉链表作为存储结构,则该哈夫曼树中总共 有( )个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m 3.设顺序循环队列 Q[0:M-1]的头指针和尾指针分别为 F 和 R,头指针 F 总是指向队头元素 的前一位置,尾指针 R 总是指向队尾元素的当前位置,则该循环队列中的元素个数为 ( ) 。 (A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M 4.设某棵二叉树的中序遍历序列为 ABCD,前序遍历序列为 CABD,则后序遍历该二叉树 得到序列为( ) 。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 5.设某完全无向图中有 n 个顶点,则该完全无向图中有( )条边。 2 2 (A) n(n-1)/2 (B) n(n-1) (C) n (D) n -1 6.设某棵二叉树中有 2000 个结点,则该二叉树的最小高度为( ) 。 (A) 9 (B) 10 (C) 11 (D) 12 7.设某有向图中有 n 个顶点,则该有向图对应的邻接表中有( )个表头结点。 (A) n-1 (B) n (C) n+1 (D) 2n-1 8.设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字 5 为基准进行一趟快 速排序的结果为( ) 。 (A) 2,3,5,8,6 (B) 3,2,5,8,6 (C) 3,2,5,6,8 (D) 2,3,6,5,8 二、填空题(24 分) 1. 为了能有效地应用 HASH 查找技术,必须解决的两个问题是 ____________________和 __________________________。 2. 下面程序段的功能实现数据 x 进栈,要求在下划线处填上正确的语句。 typedef struct {int s[100]; int top;} sqstack; void push(sqstack &stack,int x) { if (stack.top==m-1) printf(“overflow”); else {____________________;_________________;} } 3. 中序遍历二叉排序树所得到的序列是___________序列(填有序或无序) 。 4. 快速排序的最坏时间复杂度为___________,平均时间复杂度为__________。

1

5. 设某棵二叉树中度数为 0 的结点数为 N0, 度数为 1 的结点数为 N1, 则该二叉树中度数为 2 的结点数为_________;若采用二叉链表作为该二叉树的存储结构,则该二叉树中共 有_______个空指针域。 6. 设某无向图中顶点数和边数分别为 n 和 e,所有顶点的度数之和为 d,则 e=_______。 7. 设一组初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛选法建立 的初始堆为___________________________。

v1 ? ? 3? ? 2? ? 4 v 2 ? ? 1? ? 3 8. 设某无向图 G 的邻接表为 ,则从顶点 V1 开始的深度优先遍历序列为 v 3 ? ? 1? ? 4? ? 2 v 4 ? ? 1? ? 3
___________;广度优先遍历序列为____________。 三、应用题(36 分) 1. 设一组初始记录关键字序列为(45,80,48,40,22,78),则分别给出第 4 趟简单选择 排序和第 4 趟直接插入排序后的结果。 2. 设指针变量 p 指向双向链表中结点 A, 指针变量 q 指向被插入结点 B, 要求给出在结点 A 的后面插入结点 B 的操作序列 (设双向链表中结点的两个指针域分别为 llink 和 rlink) 。 3. 设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查找方法用 二分查找,要求计算出查找关键字 62 时的比较次数并计算出 查找成功时的平均查找长度。 4. 设一棵树 T 中边的集合为{(A,B),(A,C),(A,D),(B,E), (C,F),(C,G)},要求用孩子兄弟表示法(二叉链表)表示出 该树的存储结构并将该树转化成对应的二叉树。 5. 设有无向图 G(如右图所示) ,要求给出用普里姆算法构造最小 生成树所走过的边的集合。 6. 设有一组初始记录关键字为(45,80,48,40,22,78),要求 构造一棵二叉排序树并给出构造过程。 四、算法设计题(16 分) 1. 设有一组初始记录关键字序列(K1,K2,…,Kn) ,要求设计一个算法能够在 O(n)的时间 复杂度内将线性表划分成两部分, 其中左半部分的每个关键字均小于 Ki, 右半部分的每 个关键字均大于等于 Ki。 2. 设有两个集合 A 和集合 B,要求设计生成集合 C=A∩B 的算法,其中集合 A、B 和 C 用链 式存储结构表示。

2

数据结构试卷(二)参考答案
一、选择题 1.D 2.B

3.C

4.A

5.A

6.C

7.B

8.C

二、填空题 1. 构造一个好的 HASH 函数,确定解决冲突的方法 2. stack.top++,stack.s[stack.top]=x 3. 有序 2 4. O(n ),O(nlog2n) 5. N0-1,2N0+N1 6. d/2 7. (31,38,54,56,75,80,55,63) 8. (1,3,4,2),(1,3,2,4) 三、应用题 1. (22,40,45,48,80,78),(40,45,48,80,22,78) 2. q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q; 3. 2,ASL=91*1+2*2+3*4+4*2)=25/9 4. 树的链式存储结构略,二叉树略 5. E={(1,3),(1,2),(3,5),(5,6),(6,4)} 6. 略 四、算法设计题 1. 设有一组初始记录关键字序列(K1,K2,…,Kn) ,要求设计一个算法能够在 O(n)的时间 复杂度内将线性表划分成两部分, 其中左半部分的每个关键字均小于 Ki, 右半部分的每 个关键字均大于等于 Ki。 void quickpass(int r[], int s, int t) { int i=s, j=t, x=r[s]; while(i<j){ while (i<j && r[j]>x) j=j-1; if (i<j) {r[i]=r[j];i=i+1;} while (i<j && r[i]<x) i=i+1; if (i<j) {r[j]=r[i];j=j-1;} } r[i]=x; } 2. 设有两个集合 A 和集合 B,要求设计生成集合 C=A∩B 的算法,其中集合 A、B 和 C 用链 式存储结构表示。 typedef struct node {int data; struct node *next;}lklist; void intersection(lklist *ha,lklist *hb,lklist *&hc) { lklist *p,*q,*t; for(p=ha,hc=0;p!=0;p=p->next) 3

{ for(q=hb;q!=0;q=q->next) if (q->data==p->data) break; if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;} } }

4


相关文章:
数据结构试卷(二)及答案.doc
数据结构试卷(二)及答案 - 数据结构试卷(二) 一、选择题(24 分) 1.下
数据结构试题及答案(2).doc
数据结构试题及答案(2) - 数据结构试题 一、 单选题(每题 2 分,共 20
数据结构联考试卷2及答案.pdf
数据结构联考试卷2及答案 - 试卷 2 一、单项选择题 (每小题 2 分,共 30 分) 1. 在数据结构中,数据的逻辑结构可以分成( A. 动态结构和静态结构 C. 线性...
数据结构试卷2(含答案).pdf
数据结构试卷2(含答案) - 数据结构期末试卷 出卷人:09 数煤(1)班 1~
数据结构试题及答案(10套最新).doc
数据结构试题及答案(10套最新) - 一、 单选题(每题 2 分,共 20 分)
数据结构II试卷B及答案(孟凡荣).doc
数据结构II试卷B及答案(孟凡荣) - 东北大学继续教育学院 数据结构 II 试卷(作业考核 线上) B 卷 (共 8 页) 总分 题号 一二三四五六七 得分 一、单选...
数据结构试卷及答案2套.doc
数据结构试卷及答案2套 - 数据结构试卷 1 一、单项选择题:(每小题 2 分,
数据结构复习试题及答案2 (2).doc
数据结构复习试题及答案2 (2) - 一 第一套 单选题( 单选题(每题 2 分
数据结构试卷(一)及答案.doc
数据结构试卷()及答案 - 数据结构试卷(一) 数据结构试卷( 一、选择题(2
十套数据结构试题及答案.doc
十套数据结构试题及答案 - 数据结构试卷(一) 二、填空题(每空 1 分,共 2
十套数据结构试题及答案1.doc
十套数据结构试题及答案1 - 数据结构试卷(一)... 1 数据结构试卷(一)参考答案 ... 27 数据结构试卷(二)......
数据结构试题及答案(免费).doc
数据结构试题及答案(免费) - 数据结构试卷(十一) 一、选择题(30 分) 1
数据结构试卷(八)及答案.doc
数据结构试卷()及答案 - 数据结构试卷( 数据结构试卷(八) 一、选择题(3
数据结构试卷及答案.doc
数据结构试卷及答案 - …….……….密………封………线……… 期末考试《数据结
数据结构试卷一及答案.doc
数据结构试卷及答案 - 习题一 一、 选择题 ( 每小题 2 分,共 20 分 ) 1.下列程序段的时间复杂度为( )。 i=0,s=0; while (s<n) {s=s+i;i...
数据结构期中试卷及答案.doc
数据结构期中试卷及答案 - 一、选择题(每小题 2 分,共 30 分) 1. 数据结构是( D )。 A.一种数据类型 B.数据的存储结构 C.一组性质相同的数据元素的...
数据结构考试题及答案资料.doc
2012 年数据结构期末考试及答案 一、选择题 1.在数据结构中,从逻辑上可以把数据结构分为 A.动态结构和静态结构 C.线性结构和非线性结构 C 。 B.紧凑结构和...
数据结构试题(含答案).doc
数据结构试题(含答案)_工学_高等教育_教育专区。数据结构试题(含答案) 数据结
2012数据结构试卷A及答案 - 副本 (2)_图文.doc
2012数据结构试卷A及答案 - 副本 (2) - ( 密封线内不答题 ) ……
数据结构试题集(含答案).doc
数据结构试题(含答案)_哲学_高等教育_教育专区。程序复杂性 3、具有线性结构