发布时间 : 星期一 文章数据结构课程习题汇编解答更新完毕开始阅读6ff7dfea6294dd88d0d26b20
选择题
1、若入栈序列的元素顺序为A、B、C、D、E，判断下列哪一个出栈序列是不可能的。（ ）
A．A、B、C、D、E B. B、C、D、E、A C．E、A、B、C、D D. D、C、B、A、E
2、某程序的时间复杂度为（3n+nlog2n+n2+8）, 其数量级表示为（ ）。
A．O（n） B．O（nlog2n） C．O（n2） D．O（log2n）
3、一个循环队列的队首和队尾指针分别是front和rear,则判别队空的条件是（ ）
A．front+1==rear
C．front==0
B．front==rear+1 D．front==rear
4、一个非空广义表的表头（ ）
A．不可能是子表 B．只能是子表 C．只能是原子 D.可以是子表或原子 5、一个有顺序表有255个对象，采用顺序搜索法查表，平均搜索长度为（ ）
A 128 B 127 C 126 D 255
6、设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列存储空间应能够至少容纳（ ）个表项。（搜索成功的平均搜索长度为Snl=(1+1/(1-a))/2,其中a为装填因子
A 400 B 526 C 624 D 676
7、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为 ( )。
A. 4 B. 5 C. 6 D. 7 8．以下哪个数据结构不是多型数据类型（ ）
A．栈 B．广义表 C．有向图 D．字符串 9．以下数据结构中，（ ）是非线性数据结构
A．树 B．字符串 C．队 D．栈 10. 下列数据中，（ ）是非线性数据结构。
A．栈 B. 队列 C. 完全二叉树 D. 堆 11．连续存储设计时，存储单元的地址（ ）。
A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 12．对稀疏矩阵进行压缩存储目的是（ ）。
A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度 13．以下属于逻辑结构的是（ ）。
A．顺序表 B. 哈希表 C.有序表 D. 单链表
14．从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（ ）。
A．原树高度加1 B．原树高度减1 C．原树高度 D．不确定
15．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（ ）条边。
A．n B．2n C．n-1 D．n+1
16．在某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则
采用( )存储方式最节省运算时间。
A 单链表 B、仅有头指针的单循环链表C、双链表 D、仅有尾指针的单循环链表 17．下列4种排序方法中，不稳定的方法是（ ）。
A．直接插入排序 B．冒泡排序 C．归并排序 D．直接选择排序 18．串是一种特殊的线性表，其特殊性体现在（ ）
A.可以顺序存储 B.数据元素是一个字符 C.可以链接存储 D.数据元素可以是多个字符 19．在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。
A.1/2 B.1 C.2 D.4
20．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找
值为82的结点时，（ ）次比较后查找成功。
A.1 B.2 C.4 D.8 21．一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（ ）。
A.0 B.1 C.2 D.不确定
22．在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（ ）。
A.快速排序 B.希尔排序 C.冒泡排序 D.堆排序 23．向顺序栈中压入新元素时，应当（ ）。
A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针 C．先后次序无关紧要 D．同时进行 24．在线索二叉树中，下面说法不正确的是( )
A. 在中序线索树中，若某结点有右孩子，则其后继结点是它的右子树的左支末端结点。 B.线索二叉树是利用二叉树的n+1 个空指针来存放结点前驱和后继信息的。 C.每个结点通过线索都可以直接找到它的前驱和后继
D.在中序线索树中，若某结点有左孩子，则其前驱结点是它的左子树的右支末端结点。 25．广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）。Head(Tail(Head(Tail(Tail(A)))))
A. (g) B. (d) C. c D. d
26．有三个数字1,2,3,将它们构成二叉树，中序遍历序列为1,2,3的不同二叉树有( )种。
A. 5 B. 6 C. 7 D.8 27．一个算法应该是（ ）。
A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 28. 下面关于算法说法错误的是（ ）
A．算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 29. 下面说法错误的是（ ）
(1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低
A．(1) B.(1),(2) C.(1),(4) D.(3)
30．从逻辑上可以把数据结构分为（ ）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 31．以下与数据的存储结构无关的术语是（ ）。
A．循环队列 B. 链表 C. 哈希表 D. 栈 32．以下数据结构中，哪一个是线性结构（ ）？
A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 33．以下那一个术语与数据的存储结构无关？（ ）
A．栈 B. 哈希表 C. 线索树 D. 双向链表 34．一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（ ）。
A .0 B. 1 C. 2 D 不确定 35．在一棵二叉树中，第4层上的结点数最多为（ ）。
A．31 B．8 C．15 D．16 36．向堆中插入一个元素的时间复杂度为（ ）。
A．O(log2n) B．O(n) C．O(1) D．O(nlog2n)
37．广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（ ）。
A. c B. b，c C.（b，c） D.（（b，c）） 38．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）
A．250 B、500 C．254
D、501
39．计算机算法必具备输入、输出和( ) 等五个特性
A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D.易读性、稳定性和安全性
40. 下面的叙述不正确的是（ ）
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关
41．在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( ) A n-i+1 B.n-i C.i D.i-1
42．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )
A. 顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表
43．若一个具有N个顶点，K条边的无向图是一个森林(N>K)，则该森林中必有( )棵树。 A. K B. N C .N-K D.1
44．若已知一个栈的入栈序列是1，2，3，....，n，其输出序列为p1,p2,p3,?pn,若p1是n，则pi是 ( )
A. i B. n-i C. n-i+1 D. 不确定 45．表达式a*(b+c)-d的后缀表达式是( )
A.abcd*+- B.abc+*d- C .abc*+d- D.-+*abcd 46．在倒排文件中，通常包含有 ( ) 倒排表。
A. 一个 B.多个 C.两个 D.一个或两个
47．二维数组M[i,j]的元素占三个字节，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3，5]的起始地址与M按列存储时元素( ) 的起始地址相同。
A、 M[2,4] B、M[3,4] C、M[3,5] D、M[4,4]
48．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（ ）。
A. q->next=p->next;p->next=q; B. p->next=q->next;q=p; C. q->next=p->next;p->next=q; D. p->next=q->next;q->next=p; 49．非空的循环链表head的尾结点*p满足（ ）
A. p->next =NULL B. p=NULL C. p->next=head D. p=head
50．若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，则应选（ ）
A 快速排序 B 堆排序 C 归并排序 D 基数排序。 51．二叉树在线索化后，仍不能有效求解的问题是（ ）。
A.先序线索二叉树中求先序后继 B. 中序线索二叉树中求中序后继 C.中序线索二叉树中求中序前驱 D. 后序线索二叉树中求后序后继
52．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的