数据结构-模拟试卷1
二、填空题(本大题共10小题，每小题2分，共20分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.数据的逻辑结构描述数据元素之间的逻辑关系（或关系）与存储方式无关。
17.在一个长度为100的顺序表中删除第10个元素时，需移动_90_个元素。
18.队列的队尾位置通常是随着入队操作而变化的。 19.两个空串联接得到的串的长度为_0_。
20.设对称矩阵A 压缩存储在一维数组B 中，其中矩阵的第一个元素a 11存储在B[0]，元素a 52存储在B[11]，则矩阵元素a 36存储在B[17]中。
21.已知一棵哈夫曼树含有60个叶子结点，则该树中共有59_个非叶子结点。
22.如图所示的有向图中含有
2个强连通分量。
23.已知一组关键字为{15，36，28，97，24，78，47，52，13，86}，其中每相邻两个关键字构成一个有序子序列。对
这些子序列进行一趟两两归并的结果是[ 15，28，36，97，24，47，52，78，13，86 ]
16．数据的逻辑结构是从逻辑关系上描述数据，它与数据的
存储（或存储结构）无关，是独立于计算机的。 17．在一个带头结点的单循环链表中，p 指向尾结点的直接前驱，则指向头结点的指针head 可用p 表示为head= p －＞next －＞next 。
18．栈顶的位置是随着 进栈 和退栈 操作而变化的。 19．在串S=“structure ”中，以t 为首字符的子串有12个。 20．假设一个9阶的上三角矩阵A 按列优先顺序压缩存储在
一维数组B 中，其中B[0]存储矩阵中第1个元素a 1,1,则B[31]中存放的元素是
a 4,8
21．已知一棵完全二叉树中共有768结点，则该树中共有384 个叶子结点。
22．已知一个图的广度优先生成树如右图所示，则与此相 应的广度优先遍历序列为abefcdg
23．在单链表上难以实现的排序方法有快速排序、堆排序、希尔排序
24．在有序表（12，24，36，48，60，72，84）中二分查找
关键字72时所需进行的关键字比较次数为 2 25．多重表文件和倒排文件都归属于 .多关键字 文件。 24.从空树起，依次插入关键字1l ，27，35，48，52，66和73构造所得的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度为4_
25.控制区间和控制区域是VSAM_文件的逻辑存储单位。 17.在链表的结点中，数据元素所占的存储量和整个结点所占
的存储量之比称作_存储密度_。 18.已知链栈的结点结构为
栈顶指针为top ，则实现将指针p 所指结点插入栈顶的语句依次为
_____。
19.空串的长度是_0空格串的长度是_串中包含的空格数。 20.假设一个6阶的下三角矩阵B 按列优先顺序压缩存储在一
维数组A 中，其中A ［0］存储矩阵的第一个元素b 11,则A ［14］存储的元素是_b0,
21.在一棵度为3的树中，度为2的结点个数是1，度为0的
结点个数是6，则度为3的结点个数是2。
22.如图所示的有向无环图可以排出2_种不同的拓扑序列。
date
next
23.利用筛选法将关键字序列(37，66，48，29，31，75)建成
的大根堆为(756,6,489,2,31,37。
24.对长度为20的有序表进行二分查找的判定树的高度为_5。
25.在多重表文件中，次关键字索引的组织方式是将__次关键
字相同的记录链接成一个链表。
16. 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构_。
17. 删除双向循环链表中*p的前驱结点(存在)应执行的语句是
____________。
18. 栈下溢是指在栈空_时进行出栈操作。
19. 已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返回串s 的长度。若s=″ABCDEFGHIJK″,t=″ABCD″,执行运算substr(s,strlen(t), strlen(t))后的返回值为‘EFGH’20. 去除广义表LS=(a1,a2,a3,……，a n)中第1个元素，由其余元素构成的广义表称为LS的表尾
21. 已知完全二叉树T的第5层只有7个结点，则该树共有11_个叶子结点。
22. 在有向图中，以顶点v为终点的边的数目称为v的人度_。
23. 当关键字的取值范围是实数集合时，无法进行箱排序和基数__排序。
24. 产生冲突现象的两个关键字称为该散列函数的_同义词
25. 假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中已有M个同义词的记录
三、解答题(本大题共4小题，每小题5分，共20分)
26.利用广义表的head和tail操作，可从广义表 L=((a，b)，(c，d))
中分解得到原子c，其操作表达式为
head(head(tail(L)))；
分别写出从下列广义表中分解得到b的操作表达式。
(1) L1=(a.，b，c，d)；
(2) L2=( ( (a)，(b)，(c)，(d) ) )。
(1) head ( tail ( L1 ) )
(2) head ( head ( tail ( head ( L2 ) ) ) ) 27.画出与如图所示森林对应的二叉树。
26．画出下列广义表的共享结构图形表示
P=（（（z）,(x,y)）,((x,y),x),(z)）
A
B E
C
D
F I
G J
H
27．请画出与下列二叉树对应的森林。
28．已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示
0100110010000110110110110???
??????
?
????
?? (1)画出该图的图形；
（2）根据邻接矩阵从顶点a 出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。
深度优先遍历序列为：abdce 广度优先遍历序列为：abedc
29．已知一个散列表如下图所示：
35
20
33
48
59
0 1 2 3 4 5 6 7 8 9
10 11 12
其散列函数为h(key)=key%13, 处理冲突的方法为双重散列法，探查序列为：
h i =(h(key)+i *h1(key))%m i =0,1,…，m －
1
其中 h1(key)=key%11+1 回答下列问题：
（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？
对关键字35、20、33和48进行查找的比较次数为３、２、１、１
（2）该散列表在等概率查找时查找成功的平均查找长
度为多少？
平均查找长度ASL =++++=
3211259
5
28.已知有向图G 的定义如下：
G=(V ，E)
(1)画出G 的图形； (2)写出G 的全部拓扑序列。
(1)
a
b c
d e a b e
c
d
(2) a, b, e, c, d a, e, b, c, d e, a, b, c, d
29.已知3阶B-树如图所示。
(1)画出将关键字88插入之后的B-树；
(2)画出将关键字47和66依次插入之后的B-
树。
(1)
(2)
解答题(本大题共4小题，每小题5分，共20分)
26. 假设以数组seqn ［m ］存放循环队列的元素，设变量rear 和quelen 分别指示循环队列中队尾元素的位置和元素的个数。
(1)写出队满的条件表达式； (2)写出队空的条件表达式；
(3)设m=40,rear=13,quelen=19,求队头元素的位置； (4)写出一般情况下队头元素位置的表达式。
(3)
(4)
27. 已知一棵二叉树的中序序列为ABCDEFG ，层序序列为BAFEGCD ，请画出该二叉树。
28. 画出下图所示有向图的所有强连通分量。
29. 对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。
(1)假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述
68
88
7
6
88
结果的初始关键字序列；
(2)对所举序列进行快速排序，写出排序过程。
(1)4 7 1 3 6 5 2
(2)一次划分后得（231）4（657）继续划分后得（1）2（3）（5）6（7）
四算法阅读题(本大题共4小题，每小题5分，共20分) 30．下列算法的功能是比较两个链串的大小，其返回值为：
comstr(s1,s2
-<
=
>
?
?
?
?
?
1
1
12
12
12
当
当
当
s s
s s
s s
)=
请在空白处填入适当的内容。
int comstr(LinkString s1,LinkString s2)
{//s1和s2为两个链串的头指针
while(s1&&s2){
if(s1－>date
if(s1－>date>s2－>date)return1；
S1=S1－>next ；
s2=s2－>next ；
}
if( s2(或s2!=NULL或s2&&!s1) )return if( s1(或s1!=NULL或s1&&!s2))return1； return 0 ；
}
①S1=S1－>next
②s2=s2－>next
③s2(或s2!=NULL或s2&&!s1)
④s1(或s1!=NULL或s1&&!s2)
⑤return 0
31．阅读下面的算法
LinkList mynote(LinkList L)
{//L是不带头结点的单链表的头指针
if(L&&L->next){
q=L；L=L－>next；p=L；
S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； }
return L；
}
请回答下列问题：
（1）说明语句S1的功能；
查询链表的尾结点
（2）说明语句组S2的功能；
将第一个结点链接到链表的尾部，作为新的尾结点
（3）设链表表示的线性表为（a1,a2, …,a n）,写出算法执行后的返回值所表示的线性表。
返回的线性表为（a2,a3,…,a n,a1）
32．假设两个队列共享一个循环向
量空间（参见右下图），
其类型Queue2定义如下：
typedef struct{
DateType
data[MaxSize]；
int front[2],rear[2]；
}Queue2；
对于i=0或1，front[i]和rear[i]分别为第i个队列
的头指针和尾指针。请对以下算法填空，实现第i个
队列的入队操作。
int EnQueue (Queue2*Q,int i,DateType x)
{//若第 i个队列不满，则元素x入队列，并
返回1；否则返回0
if(i<0||i>1)return 0；
if(Q－>rear[i]==Q
－>front[ ① ]return0；
Q－>data[ ② ]=x；
Q－>rear[i]=[ ③ ];
return1；
}
①
②①(i＋1)%2(或1－i)
②Q－>rear[i]
③(Q－>rear[i]＋)%Maxsize
③
33．已知二叉树的存储结构为二叉链表，阅读下面算法。
typedef struct node {
DateType data；
Struct node * next；
}ListNode；
typedef ListNode * LinkList ；
LinkList Leafhead=NULL；
Void Inorder (BinTree T)
{
LinkList s；
If(T){
Inorder(T－>lchild)；
If ((!T－>lchild)&&(!T －>rchild)){
s=(ListNode*)malloc(sizeof(ListNode))；
s－>data=T－>data；
s－>next=Leafhead；
Leafhead=s；
}
Inorder(T－>rchild)；
}
}
对于如下所示的二叉树
（1）画出执行上述算法后所建立的结构；
33.(1)Leafhe
ad
F H
G D ∧
（2）说明该算法的功能。
中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以Leafhead为头指针的逆序单链表（或按二叉树中叶子结点数据自右至左链接成一个链表）
30.假设某个不设头指针的无头结点单向循环链表的长度大于1，s为指向链表中某个结点的指针。算法f 30的功能是，删除并返回链表中指针s所指结点的前驱。请在空缺
处填入合适的内容，使其成为完整的算法。
typedef struct node {
DataType data；
struct node *next；
}*LinkList；
DataType f 30(LinkList s) {
LinkList pre，p；
DataType e；
pre=s；’
p=s->next；
while( (1) ){
pre=p;
___ ___(2) ;
}
pre ->next= (3) ;
e=p->data;
free(p);
return e;
}
(1) p->next!=s
(2) p=p->next
(3) s (或 p->next)
31.算法f31的功能是清空带头结点的链队列Q。请在空缺处填入合适的内容，使其成为一个完整的算法。
typedef struct node{
DataType data；
struct node *next；
}QueueNode；
typedef struct {
QueueNode *front；／／队头指针
QueueNode *rear；／／队尾指针
}LinkQueue；
void f 31(LinkQueue*Q) {
QueueNode*p，*s；
p= (1) ；
while(p！=NULL) {
s=p；
p=p->next;
free (s);
________(2) =NULL;
Q->rear=_______(3)_______；
}
(1) Q->front->next
(2) Q->front->next
(3) Q->front
32.假设采用动态存储分配的顺序串HString作为串的存储
结构。该类型实现的串操作函数原型说明如下：
void strinit(HString s)；／／置s为空串
int strlen(HString s)；／／求串s的长度
void strcpy(HString to，HString from)；／／将串from复制到串to
void strcat(HString to，HString from)；／／将串from联接到串to的末尾
int strcmp(HString sl，HString s2)；
／／比较串sl和s2的大小，当s1
／／返回值小于0，等于0或大于0
HString substr(HString s，int i，int m)；
／／返回串s中从第i(0≤I≤strlen(s)-m)个字符起长度为m的子串
阅读下列算法f 32，并回答问题：
(1)设串S=″abcdabcd″，T=″bcd″，V=″bcda″，写出执行f 32(S，T，V)之后的S；
(2)简述算法f 32的功能。
void f 32 (HString S, HString T, HString V) {
int m, n, pos, i;
HString news;
strinit (news) ; n=strlen(S);
m=strlen(T);
pos=i=0;
while (i<=n-m) {
if( stremp(substr(S,i,m),T)! =0)i++;
else{
strcat(news,substr(S, pos, i-pos)) ; strcat(news, V) ;
pos=i=i+m;
}
}
strcat(news,substr(S,pos,n-pos)) ;
strcpy(S,news)
}
(1) S=”abcdaabcda”
(2) 串的置换操作，用串V置换串S中的子串T
33.假设以二叉链表作为二叉树的存储结构，其类型定义如下：
typedef struct node {
char data;
struct node *lchild, *rchild; ／／左右孩子指针
} BinTNode,*BinTree；
阅读下列算法f 33，并回答问题：
(1)已知如图所示的二叉树以T为指向根结点的指针，
画出执行f 33(T)后的二叉树；
(2)简述算法 f
33的功能。
void f33(BinTree T) { if (T) {
f 33 (T - > lchild) ; f 33(T - > rchild) ;
if ( ( !T - > lchild) && T->rchild) { T - > lchild=T->rchild; T - > rchild=NULL;
} } }
(1)
(2) 对二叉树的每个结点，如果其左孩子为空（右孩子不空），则将其右孩子设置为左孩子。
26.对于单链表、单循环链表和双向链表，如果仅仅知道一个
指向链表中某结点的指针p ，能否将p 所指结点的数据元素与其确实存在的直接前驱交换?请对每一种链表作出判断，若可以，写出程序段；否则说明理由。
单链表和单循环链表的结点结构为 双向链表的结点结构为
(1)单链表
不能 因为未给出指针 所以无法找到该节点的前驱 (2)单循环链表
(3)双向链表
27.假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的
哈夫曼编码依次为：0110，10，110，111，00，0111和010。
(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注
相应字符；
(2)若这些字符在电文中出现的频度分别为：3，35，13，15，
20，5和9，求该哈夫曼树的带权路径长度。
28.当采用邻接表作为图的存储结构时，也可将邻接表中的顶
点表由顺序结构改为链表结构。
(1)请分别画出这种邻接表的顶点链表结点和边表结点，并说
明结点中各个域的作用；
date
next
prior date
next
(2)对如图所示的有向图画出这种邻接表。
29.已知4阶B-树如图所示。
(1)分别画出将关键字23和89相继插入之后的B-树。
(2)画出从插入之前的B-树中删除关键字51之后的B-树。
四、算法阅读题(每小题5分，共20分)
30.阅读下列函数algo,并回答问题：
(1)假设队列q中的元素为(2,4,5,7,8),其中“2”为队头元
素。写出执行函数调用algo(&q)后的队列q；
(2)简述算法algo的功能。
void algo(Queue *Q)
{
Stack S;
InitStack(&S);
while (!QueueEmpty(Q))
Push(&S, DeQueue(Q));
while (! StackEmpty(&S))
ＥnQueue(Q,Pop(&S));
}
(1)
(2)
31.阅读下列函数F，并回答问题：
(1)已知如图所示的二叉树以二叉链表作存储结构，rt为指向
根结点的指针。写出执行函数调用F(rt)的输出结果。
输出结果 A B D E G C F H
(2)说明函数F的功能。
void F(BinTree T)
{
Stack S;
if(T)
{
InitStack(&S);
Push(&S,NULL);
while(T)
{
printf("%c", T->data);
if(T->rchild) Push(&S,T->rchild);
if(T->lchild)T=T->lchild;
else T=Pop(&S);
}
}
}
(1)
(2)前序遍历二叉树
32.已知邻接表的顶点表结点结构为
边表结点EdgeNode的结构为
下列算法计算有向图G中顶点v i的入度。请在空缺处填入合适的内容，使其成为一个完整的算法。
int FindDegree(ALGraph *G,int i)//ALGraph为图的邻接表类型
{
int dgree, j;
EdgeNode *p; degree= (1) ;
for(j=0;j
{
p=G->adjlist［j］. firstedge;
while ( (2) )
{
if( (3) )
{
degree++;
break;
}
p=p->next;
}
}
return degree;
}
(1)0
33.已知单链表的结点结构为
下列算法对带头结点的单链表L进行简单选择排序，使得L 中的元素按值从小到大排列。
请在空缺处填入合适的内容，使其成为完整的算法。
void SelectSort(LinkedList L)
{
LinkedList p,q,min;
DataType rcd;
p= (1) ;
while(p!=NULL) {
min=p;
q=p->next;
while(q!=NULL){
if( (2) )min=q;
q=q->next;
}
if( (3) ){
rcd=p->data;
p->data=min->data;
min->data=rcd;
}
vertex firstedge
adjvex next
data next
(4) ;
}
}
34．阅读下列函数arrange()
int arrange(int a[],int 1,int h,int x)
{//1和h分别为数据区的下界和上界
int i,j,t；
i=1；j=h；
while(i while(i while(i if(i { t=a[j]；a[j]=a[i]；a[i]=t；} } if(a[i] else return i－1； } （1）写出该函数的功能； 该函数的功能是：调整整数数组a[]中的元素并返回分界值i， 使所有＜x的元素均落在a[1..i]上，使所 有≥x的元素均落在a[i＋1..h]上。 （2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调 整到数组的低下标端，将所有正数均调整到数组的 高下标端，若有零值，则置于两者之间，并返回数 组中零元素的个数。 int f(int b[],int n) 或 int f(int b[],int n) { { int p,q； int p,q； p=arrange(b,0,n－1,0)； p=arrange(b,0,n－1,1)； q= arrange(b,p+1,n－1,1)；q= arrange(b,0,p,0)； return q－p； return p －q； } } 30. 阅读下列算法，并回答问题： (1)设顺序表L=(3,7,11,14,20,51)，写出执行f30(&L,15)之后的L； (2)设顺序表L=(4,7,10,14,20,51)，写出执行f30(&L,10)之后的L； (3)简述算法的功能。 void f30(SeqList*L, DataType x) { int i =0, j; while (i if(i for(j=i+1;j L->data［j-1］=L->data［j］; L->length--; } else { for(j=L->length;j>i;j--) L->data［j］=L->data［j-1］; L->data［i］=x; L->length++; } } (1)（3,，711,14,15,20,51） (2)（4,7，14,20,51） (3)当非递减循序表中存在元素X时，从表中删除该元素否则将X保存插入到顺序表中 31. 已知图的邻接表表示的形式说明如下： #define MaxNum 50 //图的最大顶点数 typedef struct node { int adjvex; //邻接点域 struct node *next; //链指针域 } EdgeNode; //边表结点结构描述 typedef struct { char vertex; //顶点域 EdgeNode *firstedge; //边表头指针 } VertexNode; //顶点表结点结构描述 typedef struct { VertexNode adjlist ［MaxNum ］; //邻接表 int n, e; //图中当前的顶点数和边数 } ALGraph; //邻接表结构描述 下列算法输出图G 的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。 typedef enum {FALSE, TRUE} Boolean; Boolean visited ［MaxNum ］; void DFSForest(ALGraph *G){ int i; for(i=0;i ［ i ］ = (1) ; for(i=0;i void DFSTree(ALGraph *G, int i) { EdgeNode *p; visited ［i ］=TRUE; p=G->adjlist ［i ］. firstedge; while(p!=NULL){ if(!visited ［p->adjvex ］){ printf(″<%c,%c>″,G->adjlist ［i ］. vertex, G->adjlist ［p->adjvex ］. vertex); (2) ; } (3) ; } } (1) (2) (3) 32. 阅读下列算法，并回答问题： (1)假设数组L ［8］={3,0,5,1,6,4,2,7}，写出执行函数调用f32(L ，8)后的L ； (2)写出上述函数调用过程中进行元素交换操作的总次数。 void f32(int R ［］,int n){ int i,t; for (i=0;i R ［i ］=t; } } (1) (2) 33. 已知带头结点的单链表中的关键字为整数，为提高查找 效率，需将它改建为采用拉链法处理冲突的散列表。设散列 表的长度为m ，散列函数为Hash(key)=key%m 。链表的结点结构为： 。请在空缺处填入适当内容，使其成 为一个完整算法。 void f33 (LinkList L, LinkList H ［］, int m) {//由带头结点的单链表L 生成散列表H ，散列表生成之后原 链表不再存在 int i,j; LinkList p,q; for (i=0;i H ［i ］= (1) ; p=L->next; while(p) { key next q=p->next; j=p->key%m; (2) ; H［j］=p; (3) ; } free(L); } (1) (2) 五、算法设计题(本大题10分) 34.假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node { int data； struct node*next； } LinkNode，*LinkList； 编写算法，输入n个整数构造一个元素值互不相同的递增有序链表(即相同的整数只取一个)。算法的函数原型给定为 LinkList f 34(int n)； LinkList L,p,q,s; int e i; L=(LinkList)malloc(sizeof(LinkNode)); L->next=NULL; for( i=1;i<=n;i++ ) { scanf (“%d”,&e); p=L; q=q->next; while(q&&q->data { p=q; q=q->next; } if ( !q || q->data>e ) { s= ( LinkList ) malloc ( sizeof ( LinkNode ) ); s->data=e; s->next=q; p->next=s; } } return L; } 34.设线性表A=(a1,a2,a3,…,a n)以带头结点的单链表作为存 储结构。编写一个函数，对A进行调整，使得当n为奇数时A=(a2,a4,…,a n-1,a1,a3,…,a n)，当n为偶数时A=(a2,a4,…,a n,a1,a3,…,a n-1)。 34. 假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示： typedef char DataType; typedef struct node { DataType data; struct node *lchild, *rchild; //左右孩子指 针 struct node *parent; //指向双亲的指针 } BinTNode; typedef BinTNode *BinTree; 若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。 (1)就后继的不同情况，简要叙述实现求后继操作的方法； (2)编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。 数据结构试卷1 一、单项选择题：(每小题2分，共20分) 1. 在一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的数据平均比较次数为________。 A. n B. n/2 C.(n+1)/2 D.(n-1)/2 2. 不带头结点的单链表first为空的判定条件是_________。 A. first->next == NULL; B. first == NULL; C. first->next == first; D. first != NULL; 3. 栈的插入和删除操作在__________进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 4. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为__________。 A. front==rear B. front!=NULL C. rear!=NULL D. front==NULL 5. 设有一个广义表A ( (x, (a, b) ), (x, (a, b), y) )，运算Head (Head (Tail (A) ) ) 的执行结果为________。 A．y B．(a, b) C．(x,(a,b)) D．x 6. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于_________。 A. n B. n-1 C. n+1 D. 2*n 7. 利用n个值作为叶结点的权重，生成的霍夫曼树中共包含有_________个结点。 A. n B. n+1 C. 2*n D. 2*n-1 8. 设无向图的顶点个数为n，则该图最多有________条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 9. 任何一个无向连通图的最小生成树_________。 A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在 10. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为_______排序法。 A．选择B.二路归并C.交换 D.插入 二、填空题（每空1分，共20分） 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的____________以及它们之间的___________和运算等的学科。 2. 顺序表中逻辑上相邻的元素的物理位置________相邻。单链表中逻辑上相邻的元素的物理位置__________相邻。 3. 在单链表中，除了首元结点外，任一结点的存储位置由___________________ 指示。 4. ________ 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性 一、填空题（共20分，每空1分）。 1.数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表 示，通常有下列四种存储结构：（1）、（2）、（3）和（4）。 2.评价算法的标准很多，通常是以执行算法所需要的（5）和所占用的（6）来判别一 个算法的优劣。 3.队列操作的原则是（7），栈的插入和删除操作在（8）进行。 4.对循环队列Q，它的最大存储空间是MAXSIZE，队头指针是front，队尾指针是rear， 采用少用一个存储单元的方法解决假溢出时，队满的判断条件是（9），队空的判断条件是（10）。 5.在以head 为表头指针的带有头结点的单链表和循环单链表中，判断链表为空的条件分 别为（11）和（12）。 6.假设二维数组A[6][8]，每个元素用相邻的4个字节存储，存储器按字节编址，已知 A[0][0]的存储位置为100，按行优先顺序存储的元素A[2][5]的第一个字节的地址为（13）。 7.空格串的长度为串中所包含（14）字符的个数，空串的长度为（15）。 8.有向图G 用邻接矩阵A[n][n] 存储表示，其第i 行的所有元素之和等于顶点i 的 （16）。 9.在关键字序列(12 ，23 ，34 ，45 ，56 ，67 ，78 ，89 ，91) 中折半查找 关键字为89和25的结点时，所需进行的比较次数分别为（17）和（18）。 10.请说出两种处理哈希冲突的方法（19）、_（20）_。 二、选择题（共20分，每题2分）。 1.对线性表，在下列哪种情况下应采用链式存储结构？（） A.经常需要随机存取元素 B.经常需要进行插入和删除操作 C.表中元素的个数不变 D.表中元素需要占据一片连续的存储空间 2.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功情况下，则平均比 较（）个结点。 A.n B.n/2 C.(n-1)/2 D.(n+1)/2 3.若对某线性表最常进行的操作是在最后一个元素之后插入和删除第一个元素，则采用 （）存储方式最节省运算时间。 A.单链表 B.双链表 C.仅有头指针的单循环链表 D.仅有尾指针的单循环链表 4.在一个单链表中，若要删除p指针所指结点的后继结点，则执行（）。 A.p=p->next; p->next=p->next->next; B.p->next=p->next->next; C.p=p->next; D.p=p->next->next; 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 国家二级ACCESS机试选择题（数据结构与算法）模拟试卷3 (总分：60.00，做题时间：90分钟) 一、选择题(总题数：30，分数：60.00) 1.在最坏情况下 （分数：2.00） A.快速排序的时间复杂度比冒泡排序的时间复杂度要小 B.快速排序的时间复杂度比希尔排序的时间复杂度要小 C.希尔排序的时间复杂度比直接插入排序的时间复杂度要小√ D.快速排序的时间复杂度与希尔排序的时间复杂度是一样的 解析：解析：按平均时间将排序分为四类：①平方阶(O(n 2 ))排序：各类简单排序，例如直接插入、直接选择和冒泡排序；②线性对数阶(O(n。log2n))排序：如快速排序、堆排序和归并排序；③O(n1+§))排序：§是介于0和1之间的常数。希尔排序便是一种；④线性阶(O(n))排序：本程序中的基数排序，此外还有桶、箱排序。 2.在深度为7的满二叉树中，度为2的结点个数为 （分数：2.00） A.64 B.63 √ C.32 D.31 解析：解析：因为在任意的二叉树中，度为O的结点(即叶子结点)总比度为2的结点的个数多1个，而度为0的结点数n 0 =2 m-1 (其中m为二叉树的深度)。本题的度为0的结点个数n 0 =2 7-1 =2 6 =64。因此，度为2的结点数n 2 =n 0 -1=63。所以选项B正确 3.设栈的顺序存储空间为S(1：m)，初始状态为top=m+1。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为 （分数：2.00） A.30 B.20 C.m-19 √ D.m-20 TOP指针向上移动一位。当压入第一个元素时，TOP指针指向m+1-1=m；当压入第二个元素时，TOP指针指向 1n+1．2=m．1；…以此类推，当压入第N个元素时，TOP指针指向m+1-N=20；则N=m+1-20=m-19。因此选项C正确。 4.算法空间复杂度的度量方法是 （分数：2.00） A.算法程序的长度 B.算法所处理的数据量 C.执行算法所需要的工作单元 D.执行算法所需要的存储空间√ 解析：解析：算法空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，因此选项D正确。 5.设循环队列为Q(1：m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为 （分数：2.00） A.4 √ B.6 C.m-5 计算机专业基础综合（数据结构）模拟试卷1 (总分：72.00，做题时间：90分钟) 一、单项选择题(总题数：21，分数：42.00) 1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数： 2.00）__________________________________________________________________________________________ 解析： 2.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是( )。 （分数：2.00） A.单链表 B.带有头指针的单循环链表 C.双链表 D.带有尾指针的单循环链表√ 解析：解析：在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、带有头指针的单循环链表、双链表都不合适。考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以答案是D。 3.已知两个长度分别为l和s的降序链表，若将它们合并为一个长度为l+s的升序链表，则最坏情况下的时间复杂度是( )。 （分数：2.00） A.O(l) B.O(ls) C.O(min(l，s)) D.O(max(l，s)) √ 解析：解析：在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是m和n中的最大值。 4.线性表中存放的主要是( )。 （分数：2.00） A.整型常量 B.字符 C.数据元素√ D.信息元素 解析：解析：线性表中主要存放的是数据元素，而数据元素可以是整型也可以是字符型，但对于一个线性表来说，所有的数据元素的类型必须相同。 5.下面的叙述中正确的是( )。 I．线性表在链式存储时，查找第i个元素的时间同i的值成正比Ⅱ．线性表在链式存储时，查找第i个元素的时间同i的值无关Ⅲ．线性表在顺序存储时，查找第i个元素的时间同i的值成正比 （分数：2.00） A.仅I √ B.仅Ⅱ C.仅Ⅲ D.I、Ⅱ、Ⅲ 解析：解析：在线性表链式存储结构中，查找第i个元素的时间与i的位置成正比。而在顺序存储结构中查找第i个元素的时间与i的位置无关。 6.对于某线性表来说，主要的操作是存取任一指定序号的元素和在最后进行插入运算，那么应该选择( )存储方式最节省时间。 （分数：2.00） A.顺序表√ 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) 模拟试卷三 一、单选题（每题 2 分，共20分） 1.对一个算法的评价，不包括如下（）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题（每题 6 分，共24分） 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N） 的联系时，称这种结构为_____________________。 2.队列的插入操作是在队列的_________进行，删除操作是在队列的__________进行。 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件 是_____________________。 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j 从0到3 ，则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 6.广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 7.二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结 点的度的总和是_____________。 8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由 算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的 一．选择题（每小题1分，共8分） 1.设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主存储，a[0][0]的存储地址为100，每个元素占1个地址空间，则a[3][2]的地址为（）。 （A）102 （B）105 （C）106 （D）108 2.森林转换为二叉树后，从根结点开始一直沿着右子数下去，一共有4个结点，表明（）。 （A）森林有4棵树（B）森林的最大深度为4 （C）森林的第一棵树有4层（D）森林有4个结点 3.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）。 （A）e （B）2e （C）n^2－e （D）n^2－2e 4.在内部排序中，排序时不稳定的有（）。 （A）插入排序（B）冒泡排序（C）快速排序（D）归并排序 5.设一数列的顺序为1，2，3，4，5，通过栈结构不可能派成的顺序数列为（）。 （A）3，2，5，4，1 （B）1，5，4，2，3 （C）2，4，3，5，1 （D）4，5，3，2，1 6.一个n条边的连通无向图，其顶点的个数至多为（）。 （A）n－１（B）n（C）n＋１（Ｄ）nlog2n 7.总共3层的完全二叉树，其结点数至少有（）个。 （A）3 （B）4 （C）7 （D）8 8.已知某算法的执行时间为（n^3+n^2+n）log2（n+2），n为问题规模，则该算法的时间复杂度是（）。 （A）O（n）（B）O（n^2） （C）O（log2n）（D）O（n^3log2n） 二．判断题（每题1分，共8分。正确的打√，错误的打×） 1.只要是算法，肯定可以在有限的时间内完成。（） 2.无论是线性表还是树，每一个结点的直接前驱结点最多只有一个。（） 3.不论是行优先还是列优先，二维数组的最后一个元素的存储位置是一样的。（） 4.直接插入排序时，关键码的比较次数与记录的初始排列无关。（） 5.二叉树的先序遍历不可能与中序遍历相同。（） 6.任何一棵二叉树，不可能没有叶子结点。（） 7.一个稀疏矩阵采用三元组法存储不可能是（5，3，7），（5，4，4），（5，3，5）。（） 8.一个无序的顺序表不能采用折半查找法进行查找。（）。 数据结构模拟考试试卷(2卷) 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打×） （√）1.数据的逻辑结构是独立于计算机的。 （×）2.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。 （√）3.栈的特点是“后进先出”。 （√）4.判断顺序队列为空的标准是头指针和尾指针均指向同一个结点。 （×）5.串的堆分配存储是一种静态存储结构。 （×）6.完全二叉树一定是满二查树。 （×）7.邻接表只能用于有向图的存储。 （×）8.选择好的哈希函数就可以避免冲突的发生。 n)。 （√）9.对于n个记录的集合进行归并排序，所需的平均时间为O (nlog 2 （×）10.对于满足二分查找和分块查找条件的文件而言，无论它存放在何种介质上，均能进行顺序查找，折半查找和分块查找。 二．填空题 1．数据结构是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的关系和运算的学科。 2．数据的存储结构形式包括：顺序存储、链式存储、散列存储、索引存储。3．在线性表的顺序存储中，元素之间的逻辑关系是通过相邻位置决定的。 4．在双向链表中，每个结点都有两个指针域，它们一个指向其前趋结点，另一个指向其后继结点。 5．在有n个元素的栈中，出栈操作的时间复杂度为 O（1）。 6．在栈结构中，允许插入、删除的一端称为栈顶。 7．对于队列，只能在队首删除元素。 8．循环队列SQ经过InitQueue (SQ)，SQ->front等于0 。 9．空格串的长度等于空格的个数。 10．设目标T="abccdcdccbaa"，模式P="cdcc"，则第 6 次匹配成功。11．采用二叉链表存储的n个结点的二叉树，一共有2n 个指针域。 12．给定如下图所示的二叉树，其前序遍历序列为：ABEFHCG 。Array 13．图的逆邻接表存储结构只适用于 __有向____图。 14．一个图的生成树的顶点是图的 _ 全部____顶点。 学习-----好资料 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是_____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2 模拟题 一．单项选择题 1. 如图所示的4棵二叉树中，哪一个是平衡二叉树 A. B. C. D. 2. 若一个算法的语句频度之和为T(n)=3n+ nlog2n + n2,则算法的时间复杂度为。 A. nlog2n + n2 D.nlog2n 3. 插入和删除操作只能在同一端进行的线性表，成为。 A.队列 B.循环队列 C.栈 D.循环栈 4. 一棵树Tr转换成相应的二叉树Bt，那么对Tr的后序遍历是对Bt的。 A．先序遍历B．中序遍历C．后序遍历D．无法确定 5. 判定一个循环队列Q（最多元素为m0）为空的条件是。 A．= =Q. Rear B. = =( + 1 ) % m0 C．!= D. != ( Q . rear +1 ) % m0 6. 广义表(（a,b,( ),c),(d,(e))，（）)的长度是。 .4 C 7. 在一个无向图中，所有顶点的度数之和，是其所有边数之和的倍。 A．1/2 B．1 C．2 D．4 8. tail（head（（a，b），c，（c，d）））的结果是。 A．b B．（b）C．（a，b）D．（c，d） 9. 深度为k的满二叉树有个分支 ．．结点。 -2 C +1 10.一棵有n个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的左子树上共有个结点。 A．n-2 B．n-1 C．n+1 D．n+2 11. n个顶点的带权无向连通图的最小生成树包含条边。 2 +1 12. 如图，若从顶点a出发按广度优先法进行遍历，可能得到的一种顶点序列是。 A．abcedf B．abcefd C．aebcfd D．acfdeb 13. 无向图的邻接矩阵是矩阵。 A.对称 B.上三角 C.下三角 D.稀疏 14.一个无向连通网图的最小生成树。 A．可能不存在B．只有一棵C．一定有多棵D．有一棵或多棵 15. 在下面给出的各种排序算法中，只有是稳定排序算法。 A．堆排序B．快速排序C．直接选择排序D．冒泡排序 2009年全国自考数据结构模拟试卷(一) 一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项目中只有一个是符号题目要求的,请将其代码填写的括号内.错选、多选或未选均无分。 1. 任何一个带权的无向连通图的最小生成树() A. 只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在 答案：B 2. Aarr和Barr两个数组的说明如下： VARAarr:Array［0··7］of char; Barr:Array［-5··2,3,··8］of char; 这两个数组分别能存放的字符的最大个数是() A. 7和35 B. 1和5 C. 8和48 D. 1和6 答案：C 3. 下列说法中正确的是() A. 任何一棵二叉树中至少有一个结点的度为2 B. 任何一棵二叉树中的每个结点的度为2 C. 任何一棵二叉树中的度肯定等于2 D. 任何一棵二叉树中的度可以小于2 答案：D 4. 二分查找算法要求被查找的表是() A. 键值有序的链表 B. 键值不一定有序的链表 C. 键值有序的顺序表 D. 键值不一定有序的顺序表 答案：C 5. 设图G采用邻接表存储，则拓扑排序算法的时间复杂度为() A. O(n) B. O(n+e) C. O(n2) D. O(n×e) 答案：B 6. 设数组data［0..m］作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为() A. front:＝front+1 B. front:＝(front+1)mod m C. rear:＝(rear+1)mod m D. front:＝(front+1)mod (m+1) 答案：D 7. 设串s1=′ABCDEFG′,s2=′PQRST′,函数con(x,y)返回x和y串的连(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的 con(subs(s1,2,len(s2)),subs(s1,len(s2),2)的结果串是() A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 答案：D 8. 设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是() A. A B. B C. C D. D 答案：D 9. 森林T中有4棵树 ，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4，那么当把森林T转换成一棵二叉树后，其根结点的左孩子上有() 个结点。 A. n1-1 B. n1 C. n1+n2+n3 D. n2+n3+n4 答案：A 10. 对广义表((a),(b))进行下面的操作head(head((a),(b)))后的结果是() A. a B. (a) 数据结构设计课程代码：7399 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 《数据结构与算法》模拟试卷五 一、名词解释（5*3=15分） 数据结构完全二叉数 AOE网队列拓扑排序 二、填空题（1*16=16分） 1.在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为 ______。 2.已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点 的条件是______。 3.如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出 栈序列中第30个元素为______。 4.一种抽象数据类型包括______和______两个部分。 5.线性表的链式存储方式中，每个结点包括两个域，分别是______和______ 。 6.在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为 空的条件分别为单链表中______ 和 ______ 。 7.在一棵二叉树中，度为0的结点的个数是10，则度为2的结点个数是_________ 8.一个有n个结点的二叉树的深度最大为___________，最小为__________ 9.n个定点的连通图至少有_______条边。 10.二分查找的存储结构仅限于________，且是__________ 11.在对一组记录(54，38，96，72，60，15，60，45，83)进行直接插入排序时， 当把第6个记录60插入到有序表时，为寻找插入位置需比较________次。 三、选择题（1*10=10分） 1.在一个不带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点， 则执行 _______。 A、HL=p; p->next=HL; B、p->next=HL; HL=p; C、p->next=HL; p=HL; D、p->next=HL->next; HL->nxet=p; 2.在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n+1）时， 需要从前向后依次移动_______个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3.在一个顺序队列中，队首指针指向队首元素的_______位置。 A、当前 B、后一个 C、前一个 D、后面 4.计算递归函数如不用递归过程通常借助的数据结构是____。 A、线性表 B、双向队列 C、树 D、栈 5.如果T2是由有序树T转换来的二叉树，则T中结点的后序排列是T2结点的 ____。 A、先序排列 B、中序排列 C、后序排列 D、层序排列 6.栈的插入和删除操作在_____进行。 四川大学 《数据结构与算法分析》课程 考试模拟试卷 模拟试卷一 一、单选题（每题2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左孩 子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有双 亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};数据结构试卷及答案2套
数据结构模拟试题1
数据结构模拟试题及答案
国家二级ACCESS机试选择题(数据结构与算法)模拟试卷3
计算机专业基础综合(数据结构)模拟试卷1
数据结构模拟试题1
《数据结构》模拟试卷一及答案
数据结构与算法 模拟试卷三四及参考答案
数据结构模拟试题9
数据结构模拟考试试卷2
数据结构模拟试题一及答案汇编
数据结构模拟卷(含答案)经典习题
数据结构模拟题1
2009年全国自考数据结构模拟试卷(一)及答案
数据结构模拟试卷(含答案)
数据结构与算法模拟试卷五
数据结构与算法模拟试卷一、二及参考答案