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

数据结构试卷(二)
一、选择题(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


相关文档

  • 2017_2018学年高中数学2.1空间点、直线、平面之间的位置关系2.1.3_2.1.4课时作业新人教A版必修2
  • 争鲜(上海)食品有限公司北京海淀第二餐饮分公司(企业信用报告)
  • 四川省三台中学实验学校2018-2019学年高一上学期第一次月考数学试题(精校Word版含答案)
  • 四川省三台中学2018-2019学年高三下学期第一次周考数学(文)试题 Word版含答案
  • 2018届四川省自贡市高三第一次诊断性考试政治试题 及答案
  • 四川自贡市2018届高三第一次诊断性考试理科综合能力测试(解析版)
  • 2018届四川省自贡市高三第一次诊断性考试文科综合试题 及答案 精品_图文
  • 四川省自贡市普高2018届高三上学期第一次诊断性考试文综政治试题
  • 四川省自贡市普高2013届高三数学第二次诊断性考试试卷理(无答案)_图文
  • 高中数学x恒成立、存在性问题解决办法课后作业
  • 高一数学必修一《恒成立与存在性问题》专题复习
  • 电脑版