数据结构扫把头
一、 单选题
1. 计算机算法指的是（ b ）。
A．程序 B．问题求解步骤的描述 C．调度方法 D．排序方法
2. 以下数据结构中，（a ）个是非线性数据结构。 烫光机
A．树 B．字符串 C．队 D．栈3. 对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为：（ c ）。 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1)无氨显影液4. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ b ）。 A.p->next=s;s->next=p->next B.s->next=p->next; p->next=s C.p->next=s;p->next=s->next D.p->next=s->next; p->next=s5. n个顶点的有向图中,含有向边的数目最多为( d ) A．n-1 B．n C．n(n-1)/2 D．n(n-1)
6. 循环队列存储在数组]中，则入队时的操作为（ d ）
A．rear=rear+1 B．rear=(rear+1)mod(m-1) C． rear=(rear+1)mod m D． rear=(rear+1)mod(m+1)7. 字符串’ababaabab’的next函数为（ d ）A.011232232 B.012341234 C.011122334 D. 0112342348. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为（ b ）A．9 B．11 C．15 D．不确定9. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素 A[5,8]的首地址为（ b ）。 A．BA+141 B．BA+180 C．BA+222 D．BA+22510. n个顶点的带权无向连通图的最小生成树包含(b )个顶点 A．n-1 B．n
C．n/2 D．n+1
洗肠器11．有关二叉树的下列说法正确的是（ b ）
A．二叉树的度为2 B．一棵二叉树的度可以小于2
C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2
12．关键路径是AOE网中（ a ）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C．最长回路
D．最短路径（从源点到汇点的所有路径中，经过弧的数目最多的路径）
13．若查每个记录的概率相等，则在具有n个记录的连续文件中采用顺序查查一个记录，其平均查长度ASL为（ c）。
A．(n-1)/2 B．n/2 C．(n+1)/2 D．n
14．就平均性能而言，目前最好的内部排序方法是（d ）
A．冒泡排序 B．希尔排序 C．堆排序 D．快速排序
15．已知广义表LS=((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是（ d ）
A．head(tail(LS)) B．tail (head (LS)
C．head(tail(head(tail(LS)))) D．head(tail(tail (head (LS))))
17．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：( a )
A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B. 在第i个结点后插入一个新结点（1≤i≤n）
C. 删除第i个结点（1≤i≤n）
D. 将n个结点从小到大排序
18．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ b ）。
A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s;
C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;
19. 设栈的输入序列是1，2，3，4,则（d ）不可能是其出栈序列。
A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2，
D. 4，3，1，2， E. 3，2，1，4，
20. 循环队列存储在数组]中，则入队时的操作为（ d ）。
A. rear=rear+1 B. rear=(rear+1) mod (m-1)
C. rear=(rear+1) mod m D. rear=(rear+1) mod (m+1)
21. 若已知一个栈的入栈序列是1, 2, 3, …, n，其输出序列为p1, p2，p3，…，pn，若p1=n，则pi为 ( c )
A．i B．n=i C．n-i+1 D．不确定
22．串 ‘ababaaababaa’ 的next的函数值为（ c ）。
A．012345678999 B．012121111212
C．011234223456 D．0123012322345网带窑
23．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ b ）
A．9 B．11 C．15 D．不确定
24．高度为 k的二叉树最大的结点数为（ c ）。
A．2k B．2k-1 C．2k-1 D．2k-1-1
25．边远山区的N个小村庄，现要为他们建成能互相通信的网，并且总的花费最少，这可以归结为什么问题（ d ）
A最短路径 B关键路径 C拓扑排序 D最小生成树
26．当一个有n个顶点的无向图用邻接矩阵A表示时，顶点Vi的度是（ b ）。
A． B． C． D． +
30．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第
一个记录为基准得到的一次划分结果为（ a ）。
A．(40,38,46,56,79,84) B. (40,38,46,79,56,84)
C．(38,40,46,56,79,84) D. (40,38,46,84,56,79)
31．在双向链表指针p的结点前插入一个指针q的结点操作是（ c ）。
A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；
B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;
C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;
D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;
33.在解决计算机主机与打印机之间速度不匹配的问题时，通常设置一个打印数据缓冲区，主机将要打印的数据依次写入缓冲区，而打印机则依次驱除数据打印，该缓冲区该是一个什么结构（d ）
A 堆栈 B 图 C 树 D 队列
35．串的长度是指（ b ）。
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
36．具有10个叶子结点的二叉树中有（b ）个度为2的结点。
A．8 B．9 C．10 D．ll
37. 有关二叉树下列说法正确的是（ b ）。
A．二叉树的度为2 B．一棵二叉树的度可以小于2
刮膜棒C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2
38．一个n个顶点的连通无向图，其边的个数至少为（ a ）。
A．n-1 B．n C．n+1 D．nlog2n
39．下列关于AOE网的叙述中，不正确的是（ b ）。
A．关键活动不按期完成就会影响整个工程的完成时间。
B．任何一个关键活动提前完成，那么整个工程将会提前完成。
C．所有的关键活动提前完成，那么整个工程将会提前完成。
D．某些关键活动提前完成，那么整个工程将会提前完成。
40. 已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（d ）。
A. head（tail（tail（L））） B. tail（head（head（tail（L））））
C. head（tail（head（tail（L）））） D. head(tail((tail(tail(L））））)
41．适用于折半查的表的存储方式及元素排列要求为( d )
A．链接方式存储，元素无序 B．链接方式存储，元素有序
C．顺序方式存储，元素无序 D．顺序方式存储，元素有序
42.若查每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查法查一个记录，其平均查长度ASL为(c )。
A． (n-1)/2 B. n/2 C. (n+1)/2 D. n
43．下列四个序列中，哪一个是堆（ c ）。
A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15
C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15
44．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（d ）。
A．acbed B．decab C．deabc D．cedba
二、填空题
1. 带头结点的单循环链表L中只有一个元素结点的条件是 l->next->next=null 。
2. 串中所含字符个数称为该串的_______长度 ________。
3. 深度为h的完全二叉树至少有 2^(k-1) 个结点，至多有 2^k-1 个结点。
4. 对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为 48 44 52 63 80 91 。
5．完全二叉树中，结点个数为n，则编号最大的非终端结点的编号为__n/2_向下取整 ___。
7. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。
8．在堆排序和快速排序中，若初始记录接近正序或反序，则选用 堆排序 ；若初始记录基本无序，则最好选用 快速排序 。
9. 在n个结点的单链表中要删除已知结点*p，需到它的前驱 ，其时间复杂度为 o(n) 。
10．模式串P=‘abaabcac’的next函数值序列为_01122312___ ____。
11．一棵左右子树不空的二叉树在先序线索化后，其空指针域数为: 1 。
12．对有18个元素的有序表A[1，18]做折半查，则查A[3]的比较序列的下标依次为 _ ___ _。
三、判断题：对打“√” ；错打“×”，并说明理由。
1. 数据元素是数据的最小单位。( 2 )
2. 顺序存储结构的主要缺点是不利于插入或删除操作。( 1 )
3. 线性表的长度是线性表所占用的存储空间的大小。( 2 )
4. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ 2 ）
5. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。( 1 )
6. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。( 1 )
7. 折半查与二叉排序树的时间性能有时不相同。（ ）
8. 十字链表是无向图的一种存储结构，而邻接多重表是有向图的一种存储结构。（ 2 ）
9. 在用堆排序算法排序时，如果要使排序后的记录序列按关键字非递减有序排列，则需要采用“大根堆”。（ 1 ）
10. 强连通分量是无向图的极大强连通子图。（ 2 ）
11. 散列表的装填因子α越小，发生冲突的可能性就越小。（ 1 ）
三．算法设计题
1、 假设以带头结点的单循环链表表示队列，其中结点结构为（data，next），并且只设一个指针rear指向队尾结点，但不设头指针，请写出相应的入队：EnQueue(Li nkList &rear,ElemType x)和出队 DeQueue(Li nkList &rear,ElemType &x)算法。
2．是利用栈和队列实现对一个字符串的逆置。
3．已知Q是一个非空队列，S是一个空栈。仅用如下给定的队列和栈的ADT函数和尽量少的工作变量，使用C或C++语言编写一个算法，将队列Q中的所有元素逆置。
l 栈的ADT函数有：
void MakeEmpty(Stack &S) 置空栈
bool Push(Stack &S,DataType e) 新元素e进栈，入栈成功返回TRUE，否则返回FALSE
DataType Pop(Stack &S ) 出栈，返回栈顶值,否则返回空值
bool isSEmpty(Stack S) 判栈空否,若空返回TRUE，否则返回FALSE
l 队列的ADT函数有：
bool EnQueue(Queue &Q, DataType e) 元素e进队，入队成功返回TRUE，否则返回FALSE
DataType DeQueue(Queue &Q) 出队列，若队列非空返回队头值, 否则返回空值
bool isQEmpty( Queue Q ) . 判队列空否。若空返回TRUE，否则返回FALSE
4．下面的算法在中序线索二叉树中求结点p的中序后继，试补充完整（线索树的结点有五个域data,lchild,rchild,左、右标志域ltag、rtag，并规定标志0指向孩子，1指向线索）。
Status InorderNext(BiThrNode *p)//返回p结点的中序后继结点
{
if (__ _①_______)
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议