数据结构模拟试题

有助于对数据结构的学习

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

1..数据元素相互之间的关系成为结构，根据数据元素之间的不同特性，通常有四类基本结构，下面哪一组是正确的：

A. 集合、线性结构、树形结构、图状结构或网状结构

B. 线性结构、链表、树形结构、图状结构或网状结构

C. 广义表、线性结构、树形结构、图状结构或网状结构

D. 集合、线性表、树形结构、图状结构或网状结构

2. 下面关于线性表的叙述中，错误的是哪一个？（）

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3. 在单链表中指针p指向元素为x的结点，则实现“删除x的后继”的语句是（）

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

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

4.在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（）

A. p->next=h B. p->next=NIL

C. p->next->next=h D. p->data=-1

5. 对于栈操作数据的原则是（）。

A. 先进先出B. 后进先出C. 后进后出D. 不分顺序

6.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）

A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 6

7．下面关于串的的叙述中，哪一个是不正确的？（）

A．串是字符的有限序列B．空串是由空格构成的串

C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储

8. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）

A．求子串B．联接C．匹配D．求串长

9. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。

A. 808B. 818C. 1010D. 1020

有助于对数据结构的学习

10.已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（）。

A. head（tail（tail（L）））B. tail（head（head（tail（L））））

C. head（tail（head（tail（L））））D. head（tail(head（tail（tail（L）））)）

11.若一棵二叉树具有10个度为2的结点，则度为0的结点个数是（）

A.11 B. 10 C.12 D.9

12. 一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）

A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG

13. 一棵深度为k且有2-1个结点的二叉树称为（）

A.完全二叉树 B.顺序存储二叉树

C.满二叉树 D.链式存储二叉树

14.返回某结点的双亲结点的操作是()

A. Parent B. Child C. Value D. Root

15. n个结点的完全有向图含有边的数目（ ）。

A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）

16. 下列哪一种图的邻接矩阵是对称矩阵？（）

A．有向图B．无向图C．AOV网D．AOE网

17. 以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ ）

k

A．v1，v2，v3，v4，v5，v6，v7

B．v1，v2，v5，v4，v3，v7，v6

C．v1，v2，v3，v4，v7，v5，v6

D．v1，v2，v5，v6，v7，v3，v4

17. 下列关于AOE网的叙述中，不正确的是（）。

A．关键活动不按期完成就会影响整个工程的完成时间

B．任何一个关键活动提前完成，那么整个工程将会提前完成

C．所有的关键活动提前完成，那么整个工程将会提前完成

D．某些关键活动提前完成，那么整个工程将会提前完成

18. 下面关于二分查找的叙述正确的是()

A. 表必须有序，表可以顺序方式存储，也可以链表方式存储C. 表必须有序，而且只能从小到大排列

B. 表必须有序且表中数据必须是整型，实型或字符型D. 表必须有序，且表只能以顺序方式存储

有助于对数据结构的学习

19. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作() 型调整以使其平衡。

A.LL B. LR C.RL D.RR

20. 一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值32时，查找成功需要的比较次数是（ ）

A．2

B．3

C．4

D．8

二、填空题（没空2分，13空，共26分）

1. 高度为8的平衡二叉树的结点数至少有__________个。

2. 在一棵树中， 结点没有前驱结点。

3. 带头结点的单链表head为空的判定条件是4. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树的深度为___________，树的度为_________。

5. 不含任何字符的串称为_______。

6. AOV网是一种___________________的图。

7. 栈与队列是特殊的线性表，栈的特性用四个字描述为述为

8. 将数据元素2,4,6,8,10,12,14,16,18,20依次存放于一个一维数组中，然后采用折半查找方法查找元素12，被比较过的数组元素的下标依次为_________。

9. 线性表是具有n个 的有限序列（n>0）。

10. 若n阶矩阵A中的元满足性质aij=aji，则称为n阶矩阵。则可将n2个元压缩存储到 个元的空间中

三、简答题（4题，共24分）

1. 将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）

2. 写出下面无向图的邻接矩阵。

有助于对数据结构的学习

3. 如下图，求出其拓扑序列（只要求给出结果）

4. 知广义表A=（（（a）），（b），c，（a），（（（d，e）））），画出其一种存贮结构图（表结点第二指针指向余表）

四、应用题（每题10分，共3题 共30分）

1. 有一份电文中共使用5个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、9，试画出对应的赫夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的赫夫曼编码。

2. 求出下图中顶点1到其余各顶点的最短路径。

3. 设有 为La和Lb的有序单链表，编写程序将其合并为一个有序链表