kl800.com省心范文网

数据结构试题及答案修2


试卷一 一、 单选题(每题 2 分,共 20 分)

1. 对一个算法的评价,不包括如下()方面的内容。 A.健壮性和可读性 2. B.并行性 C.正确性 D.时空复杂度 )。

在带有头结点的单链表 HL 中,要向表头插入一个由指针 p 指向的结点,则执行( B. p->next=HL; HL=p; D. HL=p; p->next=HL; )

A. p->next=HL->next; HL->next=p; C. p->next=HL; p=HL;

3. 对线性表,在下列哪种情况下应当采用链表表示?( A.经常需要随机地存取元素

B.经常需要进行插入和删除操作 D.表中元素的个数不变 )

C.表中元素需要占据一片连续的存储空间

4. 一个栈的输入序列为 1 2 3,则下列序列中不可能是栈的输出序列的是( A. 2 3 1 B. 3 2 1 5. AOV 网是一种( A.有向图 C. 3 1 2 ) 。 C.无向无环图 D.有向无环图 )参数。 D. 1 2 3

B.无向图

7. 若需要利用形参直接访问实参时,应将形参变量说明为( A.值 B.函数 C.指针 D.引用

8. 在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有相同的( ) 。 A.行号 B.列号 C.元素值 D.非零元素个数

二、 填空题(每空 1 分,共 28 分) 1. 数据结构是指数据及其相互之间的______________。当结点之间存在 M 对 N(M:N)的联

系时,称这种结构为_____________________。 2. 3. 队列的插入操作是在队列的___尾______进行,删除操作是在队列的____首______进行。 当用长度为 N 的数组顺序存储一个栈时,假定用 top==N 表示栈空,则表示栈满的条件是

___top==0_____________。 4. 对于一个长度为 n 的单链存储的线性表,在表头插入元素的时间复杂度为_________,在表

尾插入元素的时间复杂度为____________。 7. 二叉树是指度为 2 的____________________树。一棵结点数为 N 的二叉树,其所有结点的

度的总和是_____________。 8. 对一棵二叉搜索树进行中序遍历时,得到的结点序列是一个 ______________。对一棵由算

术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的 __________________。 9. 对于一棵具有 n 个结点的二叉树,用二叉链表存储时,其指针总数为_____________个,其

中_______________个用于指向孩子,_________________个指针是空闲的。 10. 若对一棵完全二叉树从 0 开始进行结点的编号,并按此编号把它顺序存储到一维数组 A 中,

即编号为 0 的结点存储到 A[0]中。 其余类推, 则 A[ i ]元素的左孩子元素为________,右孩子元素为
1

_______________,双亲元素为____________。 11. 在 线 性 表 的 散 列 存 储 中 , 处 理 冲 突 的 常 用 方 法 有 ________________________ 和

_____________________________两种。 三、 1.
?0 ?0 ? ?0 ? ?0 ?5 ? ?0 ? 0 0

运算题(每题 6 分,共 24 分) 已知一个 6?5 稀疏矩阵如下所示,试: (1) 写出它的三元组线性表;
0 0 0 0 0 0 0 0 1 ? 0 ? ? 0 ? ? ? 2? 0 ? ? 0 ? ?

(2) 给出三元组线性表的顺序存储表示。 2. 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起, 逐个输入各个数据而生成的二叉搜索树。 3. 对于图 6 所示的有向图若存储它采用邻接表,并且每个顶点邻接表

?1 0 0 0 0 0 0 7

中的边结点都是按照终点序号从小到大的次序链接的,试写出: 从顶点①出发进行深度优先搜索所得到的深度优先生成树; 从顶点②出发进行广度优先搜索所得到的广度优先生成树; 4. 已知一个图的顶点集 V 和边集 E 分别为: V={1,2,3,4,5,6,7}; E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7> ,<6,1>,<6,2>,<6,5>}; 若存储它采用邻接表,并且每个顶点邻接表中的边 结点都是按照终点序号从小到大的次序链接的,按主教
图6

材中介绍的拓朴排序算法进行排序,试给出得到的拓朴 排序的序列。

四、 阅读算法(每题 7 分,共 14 分) 1. int Prime(int n) { int i=1; int x=(int) sqrt(n); while (++i<=x) if (n%i==0) break; if (i>x) return 1; else return 0; } (1) 指出该算法的功能; (2) 该算法的时间复杂度是多少?

2. 写出下述算法的功能: void AJ(adjlist GL, int i, int n) { Queue Q; InitQueue(Q); cout<<i<<' '; visited[i]=true;
2

QInsert(Q,i); while(!QueueEmpty(Q)) { int k=QDelete(Q); edgenode* p=GL[k]; while(p!=NULL) {int j=p->adjvex; if(!visited[j]) { cout<<j<<' '; visited[j]=true; QInsert(Q,j); } p=p->next; }}} HL 是单链表的头指针,试写出删除头结点的算法。 ElemType DeleFront(LNode * & HL) 参考答案 一、单选题(每题 2 分,共 20 分) 1.B 2.A 3.B 4.C 5.D 6.B 7.D 二、 填空题(每空 1 分,共 26 分) 1. 2. 3. 4. 5. 6.
6 1 3 4 5 6

8.A

9.D

10.C

联系 尾

图(或图结构) 首

top==0 O(1) 128 3
5 5 2 5 1 3 图7

O(n) 44 108 7. 有序 有序序列 2n 2i+1 开放定址法 快速 n-1 n-1 后缀表达式(或逆波兰式) n+1 2i+2 链接法 归并 运算题(每题 6 分,共 24 分) (3 分) (i-1)/2

3
5 1 -1 -2 5 7

8. 9. 10. 11. 12. 三、

1.

(1)

((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))

3

图8
(2) 2. 3. 三元组线性表的顺序存储表示如图 7 示。 如图 8 所示。 DFS:????? BFS:????? 4. 四、 1. 拓朴排序为: 4 3 6 5 7 2 1 阅读算法(每题 7 分,共 14 分) (1) 判断 n 是否是素数(或质数) (2)O( n ) 2. 功能为:从初始点 vi 出发广度优先搜索由邻接表 GL 所表示的图。

六、 编写算法(8 分) ElemType DeleFront(LNode * & HL) {if (HL==NULL){ cerr<<"空表"<<endl; exit(1);} LNode* p=HL; HL=HL->next; ElemType delete p; return temp; } 试卷十三 一、选择题(30 分) 1.下列程序段的时间复杂度为( ) 。 for(i=0; i<m; i++) for(j=0; j<t; j++) c[i][j]=0; for(i=0; i<m; i++) for(j=0; j<t; j++) for(k=0; k<n; k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; (A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n) temp=p->data;

2.设顺序线性表中有 n 个数据元素,则删除表中第 i 个元素需要移动( )个元素。 (A) n-i (B) n+l -i (C) n-1-i (D) i

3.设 F 是由 T1、T2 和 T3 三棵树组成的森林,与 F 对应的二叉树为 B,T1、T2 和 T3 的结点数 分别为 N1、N2 和 N3,则二叉树 B 的根结点的左子树的结点数为( (A) N1-1 (B) N2-1 (C) N2+N3
4

) 。

(D) N1+N3

4.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为( (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)

) 。

5.设指针变量 p 指向双向链表中结点 A,指针变量 s 指向被插入的结点 X,则在结点 A 的后面插 入结点 X 的操作序列为( ) 。

(A) p->right=s; s->left=p; p->right->left=s; s->right=p->right; (B) s->left=p;s->right=p->right;p->right=s; p->right->left=s; (C) p->right=s; p->right->left=s; s->left=p; s->right=p->right; (D) s->left=p;s->right=p->right;p->right->left=s; p->right=s; 7.设输入序列 1、2、3、…、n 经过栈作用后,输出序列中的第一个元素是 n,则输出序列中的第 i 个输出元素是( ) 。 (A) n-i (B) n-1-i (C) n+l -i (D) 不能确定 ) 。

8.设散列表中有 m 个存储单元,散列函数 H(key)= key % p,则 p 最好选择( (A) 小于等于 m 的最大奇数 (C) 小于等于 m 的最大偶数 (B) 小于等于 m 的最大素数 (D) 小于等于 m 的最大合数

9.设在一棵度数为 3 的树中,度数为 3 的结点数有 2 个,度数为 2 的结点数有 1 个,度数为 1 的 结点数有 2 个,那么度数为 0 的结点数有( (A) 4 (B) 5 (C) 6 )个。 (D) 7

10.设完全无向图中有 n 个顶点,则该完全无向图中有( )条边。 (A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2

14.设有向无环图 G 中的有向边集合 E={<1,2>,<2,3>,<3,4>,<1,4>},则下列属于该有向 图 G 的一种拓扑排序序列的是( ) 。 (A) 1,2,3,4 二、填空题(30 分) 1. 设指针 p 指向单链表中结点 A,指针 s 指向被插入的结点 X,则在结点 A 的前面插入结点 X 时的操作序列为:1)s->next=___________;2) p->next=s;3) t=p->data;4) p->data=___________; 5) s->data=t; 2.设某棵完全二叉树中有 100 个结点,则该二叉树中有______________个叶子结点。 3. 设某顺序循环队列中有 m 个元素,且规定队头指针 F 指向队头元素的前一个位置,队尾指针 R 指向队尾元素的当前位置,则该循环队列中最多存储_______队列元素。 6. 设一组初始记录关键字序列为(20,12,42,31,18,14,28),则根据这些记录关键字构 (B) 2,3,4,1 (C) 1,4,2,3 (D) 1,2,4,3

造的二叉排序树的平均查找长度是_______________________________。 7. 设一棵二叉树的中序遍历序列为 BDCA,后序遍历序列为 DBAC,则这棵二叉树的前序序

列为____________________。

5

8.

设用于通信的电文仅由 8 个字母组成,字母在电文中出现的频率分别为 7、19、2、6、32、

3、21、10,根据这些频率作为权值构造哈夫曼树,则这棵哈夫曼树的高度 为________________。 10. 设无向图 G(如右图所示) ,则其最小生成树上所有边的权值之和为 _________________。

三、判断题(20 分) 1. 2. 3. 4. 有向图的邻接表和逆邻接表中表结点的个数不一定相等。( ) 对链表进行插入和删除操作时不必移动链表中结点。( ) 子串“ABC”在主串“AABCABCD”中的位置为 2。( )

若一个叶子结点是某二叉树的中序遍历序列的最后一个结点, 则它必是该二叉树的先序遍历 )

序列中的最后一个结点。( 6.

用邻接矩阵作为图的存储结构时,则其所占用的存储空间与图中顶点数无关而与图中边数有

关。( ) 7. 8. 9. 中序遍历一棵二叉排序树可以得到一个有序的序列。( ) 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。( ) 顺序表查找指的是在顺序存储结构上进行查找。 ( )

10.堆是完全二叉树,完全二叉树不一定是堆。 ( ) 五、算法设计题(20 分) 1. 2. 3. 设计计算二叉树中所有结点值之和的算法。 设计将所有奇数移到所有偶数之前的算法。 设计判断单链表中元素是否是递增的算法。

参考答案 一、选择题 1.A 6.D 11.C 2.A 7.C 12.C 3.A 8.B 13.D 4.C 9.C 14.A 5.D 10.A 15.A

二、填空题 1. 7. p->next,s->data 2. CBDA 8. 6 9. 50 3. m-1 4. 6,8 5. 快速,堆 6. 8 19/7

(24,65,33,80,70,56,48) 10.

三、判断题 1.错 6.错 2.对 7.对 3.对 8.对 4.对 9.错 5.错 10.对

四、算法设计题 1.设计计算二叉树中所有结点值之和的算法。
6

void sum(bitree *bt,int &s) {if(bt!=0) {s=s+bt->data; sum(bt->lchild,s); sum(bt->rchild,s);} 2. 设计将所有奇数移到所有偶数之前的算法。 }

void quickpass(int r[], int s, int t) {int i=s,j=t,x=r[s]; while(i<j) {while (i<j && r[j]%2==0) j=j-1; r[i]=x;} 3. 设计判断单链表中元素是否是递增的算法。 if (i<j) {r[i]=r[j];i=i+1;} while (i<j && r[i]%2==1) i=i+1; if (i<j) {r[j]=r[i];j=j-1;}}

int isriselk(lklist *head) {if(head==0||head->next==0) return(1);else for(q=head,p=head->next; p!=0; q=p,p=p->next)if(q->data>p->data) return(0); return(1); } 试卷十四 一、选择题(24 分) 1.下列程序段的时间复杂度为( ) 。 i=0,s=0; while (s<n) {s=s+i;i++;} (A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2) )存储方式最节省

2.设某链表中最常用的操作是在链表的尾部插入或删除元素,则选用下列( 运算时间。 (A) 单向链表 (C) 双向链表 (B) 单向循环链表 (D) 双向循环链表

3.设指针 q 指向单链表中结点 A,指针 p 指向单链表中结点 A 的后继结点 B,指针 s 指向被插入 的结点 X,则在结点 A 和结点 B 插入结点 X 的操作序列为( (A) s->next=p->next;p->next=-s; (C) p->next=s->next;s->next=p; ) 。

(B) q->next=s; s->next=p; (D) p->next=s;s->next=q; ) 。

4.设输入序列为 1、2、3、4、5、6,则通过栈的作用后可以得到的输出序列为( (A) 5,3,4,6,1,2 (B) 3,2,5,6,4,1

(C) 3,1,2,5,4,6(D) 1,5,4,6,2,3 5.设有一个 10 阶的下三角矩阵 A(包括对角线) ,按照从上到下、从左到右的顺序存储到连续的 55 个存储单元中,每个数组元素占 1 个字节的存储空间,则 A[5][4]地址与 A[0][0]的地址之差 为( ) 。 (A) 10 (B) 19 (C) 28 (D) 55

6.设一棵 m 叉树中有 N1 个度数为 1 的结点,N2 个度数为 2 的结点,……,Nm 个度数为 m 的结 点,则该树中共有( )个叶子结点。
7

(A)

? (i ? 1) N
i ?1

m

i

(B)

?N
i ?1

m

i

(C)

?N
i ?2

m

i

1?

(D)

? (i ? 1) N
i ?2

m

i

8. 设一组权值集合 W=(15,3,14,2,6,9,16,17),要求根据这些权值集合构造一棵哈夫曼树, 则这棵哈夫曼树的带权路径长度为( (A) 129 (B) 219 ) 。 (D) 229

(C) 189

9. 设有 n 个关键字具有相同的 Hash 函数值,则用线性探测法把这 n 个关键字映射到 HASH 表中 需要做( )次线性探测。 (A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n-1)/2

10.设某棵二叉树中只有度数为 0 和度数为 2 的结点且度数为 0 的结点数为 n,则这棵二叉中共有 ( )个结点。 (A) 2n (B) n+l (C) 2n-1 (D) 2n+l

二、填空题(48 分,其中最后两小题各 6 分) 1. 设需要对 5 个不同的记录关键字进行排序,则至少需要比较_____________次,至多需要比

较_____________次。 5. 针域。 6. 设指针变量 p 指向单链表中结点 A,则删除结点 A 的语句序列为: 设一棵 m 叉树脂的结点数为 n, 用多重链表表示其存储结构, 则该树中有_________个空指

q=p->next;p->data=q->data;p->next=___________;feee(q); 7. 8. 数据结构从逻辑上划分为三种基本类型:___________、__________和___________。 设无向图 G 中有 n 个顶点 e 条边,则用邻接矩阵作为图的存储结构进行深度优先或广度优

先遍历时的时间复杂度为_________;用邻接表作为图的存储结构进行深度优先或广度优先遍历的 时间复杂度为_________。 .12. 设有向图 G 中的有向边的集合 E={<1,2>,<2,3>,<1,4>,<4,5>,<5,3>,<4,6>,

<6,5>},则该图的一个拓扑序列为_________________________。 13. 下面程序段的功能是建立二叉树的算法,请在下划线处填上正确的内容。 *lchild;________________;}bitree;

typedef struct node{int data;struct node void createbitree(bitree *&bt) { scanf(“%c”,&ch); if(ch=='#') ___________;else

{ bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; ________;createbitree(bt->rchild);} } 14. 容。 typedef struct node {int data; struct node *next;} lklist; void lklistcreate(_____________ *&head )
8

下面程序段的功能是利用从尾部插入的方法建立单链表的算法, 请在下划线处填上正确的内

{ for (i=1;i<=n;i++) { p=(lklist *)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0; if(i==1)head=q=p;else {q->next=p;____________;}} } 参考答案 一、选择题 1.A 7.A 2.D 8.D 3.B 9.D 4.B 10.C 5.B 11.B 6.D 12.D

二、填空题 1. 7. 10. 12. 4,10 2. O(nlog2n),O(n2) 3. n 4. 1,2 5. 9. n(m-1)+1 8/3 6. q->next

线性结构,树型结构,图型结构 8. (38,13,27,10,65,76,97) 11. 124653 13.

O(n2), O(n+e)

(10,13,27,76,65,97,38) lklist,q=p

struct node *rchild,bt=0,createbitree(bt->lchild) 14.

9


数据结构试卷及参考答案_2

数据结构试卷及参考答案_2_工学_高等教育_教育专区。数据结构试卷(二)一、选择题(24 分) 1.下面关于线性表的叙述错误的是( )。 (A) 线性表采用顺序存储必须...

数据结构(C语言版)第2版习题答案—严蔚敏

数据结构(C语言版)第2版习题答案—严蔚敏_计算机软件及应用_IT/计算机_专业资料...66 II 第1章 绪论 1 .简述下列概念:数据、数据元素、数据项、数据对象、数据...

十套数据结构试题及答案

十套数据结构试题及答案_IT认证_资格考试/认证_教育专区。数据结构试卷(一).....4. 后缀算式 9 2 3 +- 10 2 / -的值为___。中缀算式(3+4X)-2Y/3...

数据结构试题及答案2

2页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 数据结构试题及答案2 数据结构试题及答案数据结构试题及答案...

中南大学十套数据结构试题及答案2

中南大学十套数据结构试题及答案2_计算机软件及应用_IT/计算机_专业资料。数据结构的试卷,考前可练 数据结构试卷(一)一、单选题(每题 2 分,共 20 分) 1. ...

数据结构练习题2及答案

数据结构练习题2及答案_工学_高等教育_教育专区。数据结构练习题 2 20122012-3...二、填空题(每空 1 分,共 26 分) 填空题( 1.数据的逻辑结构被分为___...

数据结构试题及答案修改二

数据结构试题及答案修改二_从业资格考试_资格考试/认证_教育专区。试卷一 二、 填空题(每空 1 分,共 28 分) 1. 数据结构是指数据及其相互之间的___。当结点...

数据结构试题二及答案(详细)

数据结构试题二及答案(详细)_IT/计算机_专业资料。数据结构试题二及答案(详细)1 吉首大学试题库 一、 1. 1. 一、 单选题( 单选题(每题 2 分,共 20 分)...

数据结构(C语言版)(第2版)课后习题答案

数据结构(C语言版)(第2版)课后习题答案_计算机软件及应用_IT/计算机_专业资料。数据结构(C语言版)(第2版)严蔚敏 人民邮电大学 课后习题答案 ...

数据结构参考试题及答案2

数据结构参考试题及答案2 隐藏>> 一、选择题 30% 共15题,每题2分 1. 算法指的是...( ) A.计算机程序 B.解决问题的计算方法 C.排序算法 D.解决问题的...