当前位置：文档之家 › 数据结构题目A卷

数据结构题目A卷

  • 格式：docx
  • 大小：23.56 KB
  • 文档页数：5

数据结构题目A卷

2004——2005学年第一学期期末考试

《数据结构》试卷A卷

适用班级：A2981、电A0311、12、A0321、22、机A0311、信A0311、12、13、材A0311、理A0311、土A0311、12、化A0311

注：1.请考生将试题答案写在答题纸上，在试卷上答题无效。

2.凡在答题纸密封线以外有姓名、班级学号、记录的，以作弊论。

一、选择题（每题1分，共15分）

1.数据结构被形式化地定义为（D，R），其中，D是数据元素的有限集合，R是D上的（）有限集合。

A.操作

B.关系

C.存储

D.映像

2. 下面程序段的时间复杂度是（）。

for(i=1；i<＝n；i++)

for(j=1；j<＝n；j++)

a[i][j]=2*i+3*j；

A.O(n)

B.O(2n)

C.O(2n＋1)

D.O(n2)

3.线性表如采用链式存储结构时，要求内存中可用的存储单元地址是（）。

A.必须连续的

B.部分地址必须连续

C.一定是不连续的

D.连续不连续均可 4.设head是指向带头结点的单链表的指针，则判断此单链表为空表的条件是（）。

A.head==NULL

B.head->next==NULL

C.head->next==head

D.head！=NULL

5.在一个单链表中已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（）。

A.s->next=p->next；p->next=s；

B.q->next=s； s->next=p；

C.p->next=s->next；s->next=p；

D.p->next=s； s->next=q；

6. 若某线性表中最常用的操作是取第i个元素，则采用（）存储方式最节省运算时间。

A.单链表

B.顺序表

C.双链表

D.单循环链表

7.二叉树第8层上至多有（）个结点。

A.126

B.128

C.256

D.64

8.设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（）。

A.3，2，5，6，4，1

B.1，5，4，6，2，3

C.2，4，3，5，1，6

D.4，5，3，6，2，1

9.设有一个10阶的对称矩阵A，采用压缩存储只存储其下三角，以行序为

主存储，A11为第一个元素，其存储地址为1，每元素占1个地址空间，则A85的地址为（）。

A.13

B.33

C.18

D.40

10.如果结点A有3个兄弟，而且B为A的双亲，则B的度为（）。

A.3

B. 5

C. 4

D.1

11.深度为k且有（）个结点的二叉树称为满二叉树（设根结点处于第1层）。

A.2 (k-1)

B.2k

C.(2k)-1

D.2*k-1

12.折半查找过程可以用二叉树形象的说明，实际上这种方法是根结点开始到叶子的过程。假设结点数为n ，深度为d，则比较的次数不超过（）。

A.└log2n┘+1

B.└log2n┘-1

C.└log2n┘

D.┌log2n┐

13.设关键字序列为：3，7，6，9，8，1，4，5，2。进行交换排序的最小交换次数是（）。

A.6

B.7 C.8

D.20

14.一个有n个顶点的无向图最多有（）条边。

A.n

B.n（n-1）

C.n（n-1）/2

D.2n

15.任何一棵无向连通图的最小生成树（）。

A. 有一棵或多棵

B. 只有一棵

C.一定有多棵

D.可能不存在

二、简答题（每小题5分，共25分）

1．简述栈和队列的异同点。

2．简述树的结构特性，树和二叉树的区别是什么？

3．快速排序的最坏情况是什么？你认为应该怎样避免？

4．已知一棵哈夫曼树有50个叶子结点，请问其结点总数为多少？

5. 在n个结点的线性表中进行顺序查找的平均查找长度是多少？最好情况和最坏情况下的比较次数分别是多少？

三、应用题（40分）

1.（5分）已知一棵二叉树的先序遍历序列为ABCDEFGHJI，中序遍历序列为CDBAFEJHIG，请画出该二叉树。

2.（5分）给出下列稀疏矩阵的三元组表示。

15 0 0 22 0 -15

0 13 3 0 0 0

0 0 0 -6 0 0

0 0 0 0 0 0

91 0 0 0 0 0

0 0 28 0 0 0

3.（5分）用普里姆算法求出下图的最小生成树。 4.（8分）设有一组关键字（17，12，156，29，63，74,65,34）需要插入到表长为14的散列表中，请设计一个适合该散列表的散列函数，如果用线性探测法解决冲突，用设计的散列函数将上述关键字插入到散列表中，画出其结构。

5．（7分）写出如图所示树的孩子兄弟表示法并将其转换成二叉树。

6．（10分）对于如图所示的有向图，试给出

（1） 每个顶点的入度和出度； ① ④

（2） 邻接矩阵； ⑤

（3） 邻接表；

（4） 逆邻接表； ⑥

（5） 强连通分量。 ② ③

四、算法设计题（20分）

1、设计算法，从一给定的顺序表A 中删除值在x ，y(x<=y)之间的所有元素，要求以较高的效率来实现。（8分）

2、设二叉树以二叉链表存放，编写算法在二叉树中查找值为x

的结点，输出该结点在树中的层数。（12分）

V1

V3 V7

V2

V4 V5 V6 45 42 52 65 50

60 30 70 50 40

合集下载

数据结构试题及答案

数据结构试题及答案

1

吉首大学试题库

一、 一、 单选题（每题 2 分，共20分）

1. 1. 栈和队列的共同特点是( D )。A

A.只允许在端点处插入和删除元素

B.都是先进后出

C.都是先进先出

D.没有共同点

2. 2. 用链接方式存储的队列，在进行插入运算时( C ).D

A. 仅修改头指针 B. 头、尾指针都要修改

C. 仅修改尾指针 D.头、尾指针可能都要修改

3. 3. 以下数据结构中哪一个是非线性结构？( D )

A. 队列 B. 栈 C. 线性表 D. 二叉树

4. 4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 C C

A．688 B．678 C．692 D．696

5. 5. 树最适合用来表示( C )。C

A.有序数据元素 B.无序数据元素

C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据

6. 6. 二叉树的第k层的结点数最多为(D ).D

A．2k-1 B.2K+1 C.2K-1 D. 2k-1

7. 7. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( B )D

A. 1，2，3 B. 9，5，2，3

数据结构 试题

数据结构 试题

北京航空航天大学1999年硕士生入学考试

数据结构 试题

1 （20分，每小题2分）

单项选择题，从每小题后给出的答案中选择一个正确的答案填入括号内。

①若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为( )。(1≤i≤n+1)

A．O(0) B．O(1) C.O(n) D．O(n2)

② 若在线性表中采用折半查找法查找元素，该线性表应该( )。

A．元素按值有序

B．采用顺序存储结构“

C．元素按值有序，且采用顺序存储结构

D．元素按值有序，且采用链式存储结构

③ 已知一算术表达式的中缀形式为A＋B *C-D/E，后缀形式为ABC *+DE/-，其前缀形式为( )。

A. –A+B*C/DE B. –A+B*CD/E C.-+*ABC/DE D.-+A*BC/DE

④ 若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用( )遍历方法最合适。

A．前序 B．中序 C．后序 D．按层次

⑤ 利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素35要进行( )元素间的比较。

A．4次 B．5次 C. 7次 D．10次

⑥ 对二叉排序树进行( )遍历，可以得到该二叉树所有结点构成的排序序列。

A. 前序 B．中序 C．后序 D．按层次

⑦ 具有n个顶点的有向图最多有( )条边。 A．n B．n(n—1) C n(n+1) D. n2

⑧ 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。

数据结构09试卷A

数据结构09试卷A

……………………………… 装 ……………………………… 订 ………………………………… 线 ………………………………

课程________________________班级________________________姓名__________________________学号________________________

……………………………… 密 ……………………………… 封 ………………………………… 线 ………………………………

安 徽 工 业 大 学 试 题 纸（一）

安徽工业大学2008~2009学年第二学期期末考试《数据结构》试卷(A)

一、单选题（每小题1分，共10分）

1、在一个不带头结点单链表H中，若要向表头插入一个由指针p指向的结点，则执行________。

A. H=p; p->next=H; B. p->next=H; H=p;

C. p->next=H; p=H; D. p->next=H->next; H->next=p;

2、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为________。

A. 24 B. 48 C. 72 D. 53

3、在一个长度为N的线性表中顺序查找值为X的元素时，在等概率的情况下查找成功时的平均查找长度为 。

A. N B. N/2 C. (N+1)/2 D. (N-1)/2

4、栈的插入和删除操作在 进行。

A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置

数据结构模拟试卷1

数据结构模拟试卷1

第1页 《数据结构》模拟试卷1

一、 单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内。错选或未选均无分。

1. 线性表定义为 ( )

A. 一个无限序列，可以为空 B. 一个无限序列，不能为空

C. 一个有限序列，可以为空 D. 一个有限序列，不能为空

2. 以二叉链表作为二叉树的存贮结构时，在具有n个结点的二叉链表中(n>0)，空指针域的个数为 ( )

A．2n-1 B. n+1 C. n-1 D. 2n+1

3. 若一个序列的进栈顺序为1,2,3,4, 那么不可能的出栈序列是 ( )

A. 4,2,3,1 B. 3,2,1,4 C. 4,3,2,1 D. 1,2,3,4

4. 具有65个结点的完全二叉树其深度为（根的层次号为1） ( )

A. 8 B. 7 C. 6. D. 5

5. 下列排序算法中, 排序在每趟结束后不一定能选出一个元素放到其排好的最终位置上的算法是 ( )

A. 选择排序 B. 冒泡排序 C. 归并排序 D. 堆排序

6. 设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为 ( )

A. O(nlog2e) B. O(elog2n) C. O(en) D. O(n+e)

7. 如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用的查找方法是 ( )