当前位置:首页 >> 电子/电路 >> 数据结构试题及答案解析卷C

数据结构试题及答案解析卷C


数据结构试题及答案解析卷 C
一、选择题(每题 1 分,共 20 分) 1.设某数据结构的二元组形式表示为 A=(D,R),D={01,02,03,04,05,06,07,08, 09},R={r},r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>, <03,08>,<03,09>},则数据结构 A 是( ) 。 (A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构 2.下面程序的时间复杂为( ) for(i=1,s=0; i<=n; i++) {t=1;for(j=1;j<=i;j++) t=t*j;s=s+t;} 2 3 4 (A) O(n) (B) O(n ) (C) O(n ) (D) O(n ) 3.设指针变量 p 指向单链表中结点 A,若删除单链表中结点 A,则需要修改指针的操作序 列为( ) 。 (A) q=p->next;p->data=q->data;p->next=q->next;free(q); (B) q=p->next;q->data=p->data;p->next=q->next;free(q); (C) q=p->next;p->next=q->next;free(q); (D) q=p->next;p->data=q->data;free(q); 4.设有 n 个待排序的记录关键字,则在堆排序中需要( )个辅助记录单元。 2 (A) 1 (B) n (C) nlog2n (D) n 5.设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以 20 为基准记 录的一趟快速排序结束后的结果为( )。 (A) 10,15,14,18,20,36,40,21 (B) 10,15,14,18,20,40,36,21 (C) 10,15,14,20,18,40,36,2l (D) 15,10,14,18,20,36,40,21 6.设二叉排序树中有 n 个结点,则在二叉排序树的平均平均查找长度为( ) 。 2 (A) O(1) (B) O(log2n) (C) (D) O(n ) 7.设无向图 G 中有 n 个顶点 e 条边,则其对应的邻接表中的表头结点和表结点的个数分别 为( ) 。 (A) n,e (B) e,n (C) 2n,e (D) n,2e 8. 设某强连通图中有 n 个顶点,则该强连通图中至少有( )条边。 (A) n(n-1) (B) n+1 (C) n (D) n(n+1) 9.设有 5000 个待排序的记录关键字,如果需要用最快的方法选出其中最小的 10 个记录关 键字,则用下列( )方法可以达到此目的。 (A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序 10.下列四种排序中( )的空间复杂度最大。 (A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序 二、填空殖(每空 1 分 共 20 分) 1. 数据的物理结构主要包括_____________和______________两种情况。 2. 设一棵完全二叉树中有 500 个结点, 则该二叉树的深度为__________; 若用二叉链表作 为该完全二叉树的存储结构,则共有___________个空指针域。 3. 设输入序列为 1、2、3,则经过栈的作用后可以得到___________种不同的输出序列。 4. 设有向图 G 用邻接矩阵 A[n][n]作为存储结构,则该邻接矩阵中第 i 行上所有元素之和 等于顶点 i 的________,第 i 列上所有元素之和等于顶点 i 的________。 5. 设哈夫曼树中共有 n 个结点,则该哈夫曼树中有________个度数为 1 的结点。 6. 设有向图 G 中有 n 个顶点 e 条有向边,所有的顶点入度数之和为 d,则 e 和 d 的关系为 _________。

7. 8. 9. 10. 11. 12. 13.

14.

__________遍历二叉排序树中的结点可以得到一个递增的关键字序列 (填先序、 中序或 后序) 。 设查找表中有 100 个元素,如果用二分法查找方法查找数据元素 X,则最多需要比较 ________次就可以断定数据元素 X 是否在查找表中。 不论是顺序存储结构的栈还是链式存储结构的栈, 其入栈和出栈操作的时间复杂度均为 ____________。 设有 n 个结点的完全二叉树,如果按照从自上到下、从左到右从 1 开始顺序编号,则第 i 个结点的双亲结点编号为____________,右孩子结点的编号为___________。 设一组初始记录关键字为(72,73,71,23,94,16,5),则以记录关键字 72 为基准的 一趟快速排序结果为___________________________。 设有向图 G 中有向边的集合 E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>},则该图 的一种拓扑序列为____________________。 下列算法实现在顺序散列表中查找值为 x 的关键字,请在下划线处填上正确的语句。 struct record{int key; int others;}; int hashsqsearch(struct record hashtable[ ],int k) { int i,j; j=i=k % p; while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);} if (_______________________ ) return(j); else return(-1); } 下列算法实现在二叉排序树上查找关键值 k,请在下划线处填上正确的语句。 typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree; bitree *bstsearch(bitree *t, int k) { if (t==0 ) return(0);else while (t!=0) if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________; }

三、计算题(每题 10 分,共 30 分) 1.已知二叉树的前序遍历序列是 AEFBGCDHIKJ,中序遍历序列是 EFAGBCHKIJD,画出此 二叉树,并画出它的后序线索二叉树。 2.已知待散列的线性表为(36,15,40,63,22) ,散列用的一维地址空间为[0..6],假定 选用的散列函数是 H(K)= K mod 7,若发生冲突采用线性探查法处理,试: (1)计算出每一个元素的散列地址并在下图中填写出散列表: ` 0 1 2 3 4 5 6 (2)求出在查找每一个元素概率相等情况下的平均查找长度。 3.已知序列(10,18,4,3,6,12,1,9,18,8)请用快速排序写出每一趟排序的结果。 四、算法设计题(每题 15 分,共 30 分) 1. 设计在单链表中删除值相同的多余结点的算法。 2. 设计一个求结点 x 在二叉树中的双亲结点算法。

数据结构试卷(三)参考答案

一、选择题 1.B 2.B 3.A 4.A 5.A 6.B 7.D 8.C 9.B 10.D 第 3 小题分析:首先用指针变量 q 指向结点 A 的后继结点 B,然后将结点 B 的值复制到 结点 A 中,最后删除结点 B。 第 9 小题分析:9 快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出 最小的 10 个数, 而堆排序只需要在初始堆的基础上再进行 10 次筛选即可, 每次筛选的时间 复杂度为 O(log2n)。 二、填空题 1. 顺序存储结构、链式存储结构 2. 9,501 3. 5 4. 出度,入度 5. 0 6. e=d 7. 中序 8. 7 9. O(1) 10. i/2,2i+1 11. (5,16,71,23,72,94,73) 12. (1,4,3,2) 13. j+1,hashtable[j].key==k 14. return(t),t=t->rchild 第 8 小题分析:二分查找的过程可以用一棵二叉树来描述,该二叉树称为二叉判定树。 在有序表上进行二分查找时的查找长度不超过二叉判定树的高度 1+log2n。 三、计算题 1.
A E F NULL D H F K J G B C

2、H(36)=36 mod 7=1; H(15)=15 mod 7=1;….冲突 H1(15)=(1+1) mod 7=2; H(40)=40 mod 7=5; H(63)=63 mod 7=0;

H1(22)=(1+1) mod 7=2; ….冲突 H2(22)=(2+1) mod 7=3;

H(22)=22 mod 7=1; ….冲突 (1) 0 1 2 63 (2)ASL= 36 15

3

4

5

6

22

40

1? 2 ?1?1? 3 ? 1 .6 5

3、(8,9,4,3,6,1),10,(12,18,18) (1,6,4,3),8,(9),10,12,(18,18) 1,(3,4,6),8,9,10,12,18,(18) 1,3,(4,6),8,9,10,12,18,18 1,3, 4,6,8,9,10,12,18,18 四、算法设计题 1. 设计在单链表中删除值相同的多余结点的算法。 typedef int datatype; typedef struct node {datatype data; struct node *next;}lklist; void delredundant(lklist *&head) { lklist *p,*q,*s; for(p=head;p!=0;p=p->next) { for(q=p->next,s=q;q!=0; ) if (q->data==p->data) {s->next=q->next; free(q);q=s->next;} else {s=q,q=q->next;} } } 2. 设计一个求结点 x 在二叉树中的双亲结点算法。 typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; bitree *q[20]; int r=0,f=0,flag=0; void preorder(bitree *bt, char x) { if (bt!=0 && flag==0) if (bt->data==x) { flag=1; return;} else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); } } void parent(bitree *bt,char x) { int i; preorder(bt,x); for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break; if (flag==0) printf("not found x\n"); else if (i<=r) printf("%c",bt->data); else printf("not parent");


更多相关文档:

c++答案_数据结构试卷及答案

c++答案_数据结构试卷及答案_理学_高等教育_教育专区。mmmmmmmmmmmmmmmmmmmmmmm第4 章 过程抽象――函数 1 《数据结构》试卷及答案 1.算法分析的目的是( c )。...

数据结构试卷及答案

数据结构试卷及答案_院校资料_高等教育_教育专区。模拟试卷一一、 单选题(每题 ...共 20 分) 1.B 2.D 3.A 4.B 5.B 6.C 7.A 8.C 9.B 10.B ...

十套数据结构试题及答案1

十套数据结构试题及答案1_工学_高等教育_教育专区。东南大学数据结构试卷 ...A.5 B.6 C.7 D.8 三、计算题(每题 6 分,共 24 分) 1. 在如下...

数据结构C语言2016总复习(附带试卷及答案)

数据结构C语言2016总复习(附带试卷及答案)_教育学_高等教育_教育专区。数据结构,总复习,试卷数据结构”期末考试试题 一、单选题(每小题 2 分,共 12 分) ...

数据结构试题及答案

数据结构试题及答案_其它课程_高中教育_教育专区。...3. 假定一棵树的广义表表示为 A(C,D(E,F,G)...数据结构A卷试题及答案 10页 免费 十套数据结构试题...

数据结构试题及答案解析卷C

数据结构试题及答案解析卷 C 一、选择题(每题 1 分,共 20 分) 选择题( 1.设某数据结构的二元组形式表示为 A=(D,R),D={01,02,03,04,05,06,07,08...

数据结构试卷及答案

数据结构试卷及答案_教育学_高等教育_教育专区。《数据结构》期末考试一、单项...A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等...

数据结构试卷及答案

数据结构试卷及答案_教育学_高等教育_教育专区。东华理工大学 2015 —2016 学年...(5 分) A C D B G H E F I J A C G H D B E J F I 先根...

数据结构试卷及答案

数据结构试卷及答案 1.算法分析的目的是( )。 B.研究算法中输入和输出的关系 D.分析算法的易懂性和文档性 A.找出数据结构的合理性 C.分析算法的效率以...

十套数据结构试题及答案

十套数据结构试题及答案_计算机软件及应用_IT/计算机_专业资料。十套数据结构...3. 假定一棵树的广义表表示为 A(C,D(E,F,G) ,H(I,J) ) ,则树中所...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com