《数据结构》精选习题集粹

第1章 绪论

判断：（中科院1999）

顺序存储方式只能用于存储线性结构。－错

顺序查找法适用于存储结构为顺序或链接存储的线性表。－对

填空：（中科院1999）

对于给定的n个元素，可以构造出的逻辑结构有（ ）、（ ）、（ ）、（ ）四种。

－集合线性结构－树形结构－图结构

计算机算法必须具备输入、输出、（ ）等5个特性。 B.可行性、确定性和有穷性

简述算法的5个特性。

第2章 线性表

问答：（北京航空1998）

在非空双向循环表中q所指的结点后面插入p所指的结点的过程已经依次进行了3步：p->llink:=q；p->rlink:=q->rlink；q->rlink:=p；第4步应是什么动作？

－q->rlink.llink:=p

问答：若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？

－链式存储结构

简答：（北京科技大学2002）

设单链表中结点的数据域为data，指针域为next，指针p为表中某一结点的地址，请写出在p结点之前插入一个s结点的C语言描述语句。

－s->.next:=p

选择：（武汉理工2002）

指针P所指的元素是双向循环链表L的尾元素的条件是（ ） D.P->Rlink=L

一个循环链表可以由所给定的头指针或者尾指针惟一地确定。－对

写一个算法，建立双向循环链表

简答：写出在双向链表指针P之后插入结点S的操作序列

－s->right=p->right；if(p->right) p->right->left=s； s->left=p； p->right=s

选择：（南京理工2002）

在一个单链表中，若删除P结点的后继结点，则（ ）p->next=p->next->next

循环链表的主要优点是（ ）从表中任一结点出发都能遍历整个链表

第3章 栈和队列

选择：（程序员2004）

判断一个表达式中左右括号是否匹配，采用（ D.栈 ）实现较为方便

用单链表表示的链式队列的对头在链表的（ 链头 ）位置

判断：（中科院1999）

栈和队列都是取点的线性结构－正确

消除递归不一定需要使用栈－正确

栈、先进先出队列、优先级队列、双端队列等都可以看作是一个容器类的派生类。该容器代表存取位置的顺序存取结构。－正确

循环队列A[0..m-1]存放其元素，用front和rear分别表示队头和队尾，则循环队列满的条件是（ ）

A.（Q.rear+1）%m==Q.front

算法：（中科院2000）

设顺序栈S中有2n个元素，从栈顶到栈底的元素依次是a2n，a2n-1，。。。，a2，a1，要求通过一个辅助的循环队列及相应的入栈、出栈、入队、出队操作来重新排列栈中元素，使得从栈顶到栈底的元素依次是a2n，a2n-2，。。。，a4，a2，a2n-1，a2n-3，。。。，a3，a1，请写出一算法实现该操作，要求附加的空间是O(n)，时间复杂度为O(n)。

简答： A、B、C三个元素进栈S的次序是A、B、C，利用Push(S,X)，Pop(S)表示

入栈、出栈操作，写出所有可能的出栈序列和获得每个序列的相应操作，并指明哪个序列不会是出栈序列。

－CBA BCA ACB ABC BAC

－CAB

在操作序列push(1)，push(2)，pop，push(5)，push(7)，pop，push(6)之后，栈顶元素和栈底元素分别是什么？－6－1

在操作序列Qinsert(1)，Qinsert(2)，Qdelete，Qinsert(5)，Qinsert(7)，Qdelete，Qinsert(9)之后，队头元素和队尾元素分别是什么？－5－9

第4章 串

选择：（程序员2004）

字符串是一种线性表，其特殊性表现在（ 1 ）

A.它的数据元素是一个字符 B.它可以链式存储

C.它可以顺序存储 D.它的数据元素可以是多个字符

第5章 数组和广义表

选择：（程序员2005）

设数组a[1..10,5..15]的元素以行为主序存放，每个元素占用4个存储单元，则数组元素a[i,j](1≤i≤10,5≤j≤15)的地址计算公式为（ ）

A.a-204+2i+j B.a-204+40i+4j C.a-84+i+j D.a-+44i+4j

－D

选择：（程序员2004）

对于二维数组A[1..4,3..6]，设每个元素占两个存储单元，若分别以行和列为主序存储，则元素A[3,4]相对于数组空间起始地址的偏移量分别是（ 4 ）和（ 1 ）

A.12 B.14 C.16 D.18

若广义表L=((1,2,3))，则L的长度和深度分别是（ 2 ）

A.1和1 B.1和2 C.1和3 D.2和2

填空：（中国科技大学1998）

设广义表L=((),())，则Head(L)=（ ）；Tail(L)＝（ ）；L的长度是（ ）；L的深度是（ ）－Head(L)=();－Tail(L)=(());－2－2

选择：（北京邮电1998）

已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出原子项t的运算是 D.head(tail(head(tail(tail(L)))))

将一个A[1..100,1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，A中元素A66,65（即元素下标）在B中的位置K为（ 2 ）A.198 B.195 C.197

三对角线矩阵A[1..n][1..n]以行序为主顺序存储，其存储始址是B，每个元素占一个存储单元，则元素A[i][j]的存储起始地址为（ D.b+2*i+j-3 ）(1≤i,j≤n)

第6章 树和二叉树

选择：（程序员2004）

在一颗非空二叉树中，叶子节点的总数比度为2的节点总数多（ 1 ）个

在一棵完全二叉树中，其根的序号为1，可判定序号为p和q的两个结点是否在同一层。│log2p」=│log2q」

如果根的层次为1，具有61个结点的完全二叉树的高度为（ 6 ）

若二叉树的先序遍历序列为ABDECF，中序遍历序列DBEAFC，则其后序遍历序列为（ DEBFCA

由权值为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ 44 ）

（ ）的遍历仍需要栈的支持 C.后序线索树

对于前序遍历和中序遍历结果相同的二叉树为（ F.所有结点只有右孩子的二叉树，前序遍历和后序遍历结果相同的二叉树为（ ）。 B.只有根结点的二叉树

哈夫曼树是带权路径长度最短的树，路径上长度（ ）结点离根（ ）

B.较小 D.较远

简述二叉哈夫曼树的建树方法

简答：（北京科技大学2002）

设记录的关键字（key）集合K={26,36,41,44,15,68,12,6,51,25}，以K为权值集合，构建一棵哈夫曼树，依次取K中各值，构建一棵二叉排序树

判定：高度为K的二叉树至多有2k-1（k≥1）个结点－错误

选择：（南京理工2002）

在线索化二叉树中，结点t没有左子树的充要条件是B.t->ltag=1

第7章 图

选择：（程序员2004）

采用邻接表表示一有向图，若图中某顶点的入度和出度分别为d1和d2，则该顶点对应的单链表的结点数为（ ） B.d2

具有n（n>0）个顶点的无向图最多含有（ ）条边 C.n(n-1)/2

无向图中一个顶点的度是指图中（ ）C.与该顶点相邻接的顶点数

一个具有n（n>0）个顶点的连通无向图至少有（ ）条边 D.n-1

第9章 查找

选择：（软件设计师2005）

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

在常用的描述二叉排序树的存储结构中，关键值最大的结点（ ） B.右指针一定为空

已知一个线性表（38,25,74,63,52,48），假定采用散列函数h(key)=key%7计算散列地址，并散列存放在散列表A[0..6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为（ ） C.2.0

设H(x)是一哈希函数，有K个不同的关键字（x1,x2,x3,…,xk）满足H(x1)=H(x2)=…=H(xk)，若用线性探测法将这K个关键字存入哈希表中，至少要探测（ ）次 D.K(k-1)/2

第10章 内部排序

选择：（程序员2005）

从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为（ ）A.插入排序

选择：（武汉理工2002）

对n个数据进行排序，不稳定排序是（ C.Shell排序 ），快速排序是一种（ B.交换排序 ），关键字序列（ ）是一个堆 D.20,35,23,80,,76

简答：（北京科技大学2002）（清华大学1998类似）

请指出三个稳定和三个不稳定的内部排序方法

－基数排序、简单选择排序、插入排序、归并排序、冒泡排序

－快速排序、堆排序、希尔（Shell）排序

若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）为宜。直接插入

若关键字是非负整数，则下列排序中平均速度最快的排序是（ ）；若要求辅助空间

为O(1)，则平均速度最快的排序是（ ）；若要求排序是稳定的，且关键字为实数，则平均速度最快的排序是（ ）

A.直接插入排序 B.直接选择排序 C.Shell排序 D.冒泡排序

E.快速排序 F.堆排序 G.归并排序 H.基数排序

－H－F－G

判定：快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少－错误 所需额外栈空间比堆排序所需空间要大

若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是归并排序

如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快

E.简单选择排序

设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，在以下的排序方法中采用哪一种最好？为什么？A.快速排序 －可以每次对第一个子序列进行

分割，直至子序列长度小于或等于10，若长度不足10，则对每两个子序列分割出相应长度的子序列即可。