数据结构试卷及答案

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

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

《数据结构》试卷一

一、填空题：（共２０分）

1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 存储结构。

2、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是 。

3、在一棵二叉树中，度为０的结点个数为n0，度为２的个数为n2，则n0= 。

4、二叉树的前序遍历序列等同于该二叉树所对应森林的 遍历序列

5、对一棵二叉排序树，若以 遍历该树，将得到一个以关键字递增顺序排列的有序序列。

6、三个结点a,b,c组成二叉树，共有 种不同的结构。

7、在AVL树中，由于在Ａ结点的右孩子的右子树上插入结点，使Ａ结点的平衡因子由-1变为-2，使其失去平衡，应采用 型平衡旋转。

8、图的遍历有两种,它们是 。

9、堆排序的时间复杂度为 。

10、在含有N个结点的二叉链表中有 空链域，通常用这些空链域存储线索，从而得另一种链式存储结构----线索链表。

二、单项选择题（共２０分）

１、若进栈序列为１，２，３，４，假定进栈和出栈可以穿插进行，则可能的出栈序列是（ ）

（A）２，４，１，３ （B）３，１，４，２

（C）３，４，１，２ （D）１，２，３，４

２、有一棵非空的二叉树，（第０层为根结点），其第i层上最多有多少个结点？（ ）

（A） ２i（B）２1i （C） ２1i （D） i

３、设电文中出现的字母为A，B，C，D，E，每个字母在电文中出现的次数分别为９，２７，３，５，１１，按huffman编码，则字母A编码为（ ）

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

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

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

B.都是先进后出

C.都是先进先出

D.没有共同点

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

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

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

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

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

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

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

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

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

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

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

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

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

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

C. 9，5，3 D. 9，4，2，3

8. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为

A. O（1） B. O（n） C. O（1og2n） D. O（n2）