许昌学院数据结构 考试题库.docx
《许昌学院数据结构 考试题库.docx》由会员分享，可在线阅读，更多相关《许昌学院数据结构 考试题库.docx（49页珍藏版）》请在冰点文库上搜索。
许昌学院数据结构考试题库
目录
一、数据结构概念1
二、线性表1
三、栈和队列4
四、字符串，数组，广义表6
五、树型结构：
8
六、图型结构：
11
七、查找排序12
八、算法应用及分析：
18
九、2013年统考计算机考研真题23
十、2012年计算机统考真题参考答案25
十一、2013年计算机统考真题及其答案27
一、数据结构概念
1.数据结构是指【】，具体包含三个方面：
数据的【】，数据的【】和数据运算的集合。
2.根据数据元素之间关系的不同特性，通常有【】、【】、【】、【】四类基本逻辑结构，它们反映了四类基本的数据组织形式。
3.数据结构S中：
元素的集合为：
{A，B，C，D，E，F，G，H，I}，关系的集合为：
{，，，，，，，，}，则S的逻辑结构为（）
（A）集合（B）线性（C）树（D）图
4.数据元素之间存在一对多关系的数据结构是（）
（A）线性表（B）队列（C）二叉树（D）AOV-网
5.以下数据结构中，属于线性结构的有（）
（A）线性表（B）树（C）二叉树（D）图
6.存储结构是逻辑结构在计算机中的实现。
（）
7.非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。
（）
8.非空线性表中任意一个数据元素都有且仅有一个直接后继元素。
（）
9.顺序存储结构只能用来存放线性结构；链式存储结构只能存放非线性结构。
（）
10.算法就是程序。
（）
11.一种逻辑结构可以采用不同的存储方式存放在计算机中。
（）
二、线性表
12.线性结构的基本特征是:
若至少含有一个结点，则除起始结点没有直接【】外，其他结点有且仅有一个直接【】;除终端结点没有直接【】外，其它结点有且仅有一个直接【】。
13.线性表的顺序存储结构是指用一组【】的存储单元依次存储线性表中的各个元素，逻辑上相邻的元素，其物理位置【】_。
链式存储结构中，逻辑上相邻的元素，其物理位置【】。
14.线性表的顺序存储结构中，逻辑上相邻的元素，其物理位置【】。
链式存储结构中，逻辑上相邻的元素，其物理位置【】。
15.在顺序表中插入或删除一个元素，需要平均移动【】元素，具体移动的元素个数与【】有关。
16.单链表是线性表的的【】存储结构。
17.单链表表示法的基本思想是用【】表示结点间的逻辑关系。
18.循环链表与单链表的区别仅仅在于循环链表尾结点的链域值不是【】，而是一个指向【】的指针。
19.
如右图所示，在单键表中，P指针所指结点之后插入一个新结点S，操作的语句是：
【】；【】。
20.顺序表的类型中，假定每个datatype类型的变量占用k（k>=1）个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个（1≤i≤n）结点ai的存储地址为【】。
21.在单链表中，删除P指针所指向的结点的后继（S指针指向的结点）的操作是【】；free（【】）。
22.以下为顺序表的插入运算，分析算法，请在空白处填上正确的语句。
voidinsert_seqlist（seqlist*L，datatypex，inti）
/*将x插入到顺序表L的位序为i的位置*/
{if（L->last==maxsize-1）error（“表满”）；
if（（i<1）||（i>L->last+2））error（“非法位置”）;
for（j=L->last;j>=i-1;j--）【】;
L->data[i-1]=x;
【】;
}
23.以下为顺序表的删除运算，分析算法，请在空白处填上正确的语句。
voiddelete_sqlist（sqlist*L,inti）
/*删除顺序表L中的第i-1个位置上的结点*/
{if（（i<1）||（i>L->last））
error（“非法位置”）；
for（j=i+1;j=L->last;j++）
【】;
L->last=L->last-1;
}
24.下列有关线性表的叙述中，正确的是（）。
（A）一个线性表是n个数据元素的有限序列（B）线性表中任何一个元素有且仅有一个直接前驱
（C）线性表中任何一个元素有且仅有一个直接后继（D）以上说法都不正确
25.顺序表是线性表的（）。
（A）链式存储结构（B） 顺序存储结构（C） 索引存储结构（D）散列存储结构
26.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时,需向前移动（）个元素。
（A）n-i（B）n-i+1（C）n-i-1（D）i
27.一个长度为n的顺序表中第i个位置上插入新元素（1≤i≤n+1）时,需向后移动（）个元素。
（A）n-i（B）n-i+1（C）n-i-1（D）i
28.下面的定义是（）。
typedefstructnode
{intdata;
structnode*next;
}linklist;
（A）顺序表（B）单链表（C）双向链表（D）二叉链表
29.下面的定义是（）。
typedefstruct
{intdata[Maxsize];
intlast;
}seqlist;
（A）顺序表（B）单链表（C）静态链表（D）循环队列
30.单链表的一个存储结点包含（）。
（A）数据域或指针域 （B）指针域或链域 （C）指针域和链域 （D）数据域和链域
31.单链表中，增加头结点的目的是为了（）。
（A）使单链表至少有一个结点（B）标示表结点中首结点的位置
（C）方便运算的实现（D）说明单链表是线性表的链式存储实现
32.对于单链表表示法，以下说法错误的是（）。
（A）指向链表的第一个结点的指针，称为头指针
（B）单链表的每一个结点都被一个指针所指
（C）终端结点的指针域就为NULL
（D）尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表
33.有一个含头结点的单链表，头指针为head，则判断其是否为空的条件是（）。
（A）head==NULL（B）head->next==NULL（C）head->next==head（D）head!
=NULL
34.在带头结点的非空单链表H中，指针p指向某的结点，求p结点的前驱结点指针q的算法是（）。
（A）q=H;while（q!
=p）q=q->next;（B）q=H;while（q->next!
=p）q=q->next;
（C）q=H->next;while（q!
=p）q=q->next;（D）q=H->next;while（q->next!
=p）q=q->next;
35.在带头结点的单链表H中，求单链表长度len的算法是（）。
（A）len=0,p=H;while（p->next!
=NULL）{len++;p=p->next;}
（B）len=0,p=H->next;while（p->next!
=NULL）{len++;p=p->next;}
（C）len=1,p=H;while（p!
=NULL）{p=p->next;len++;}
（D）len=1,p=H->next;while（p->next!
=NULL）{p=p->next;len++;}
36.假设指针p指向单链表中的某一结点,s为某结点指针，则在p指针后面插入结点s的操作是（）。
（A）p->next=s;s=p->next;（B）p->next=s;s->next=p->next;
（C）s->next=p->next;p->next=s;（D）s->next=p;p->next=s;
37.假设指针p指向单链表中的某一结点,s为某结点指针，则在p指针前面插入结点s的操作是（）。
（A）s->next=p->next;p->next=s;（B）p->next=s;s->next=p->next;
（C）p->next=s;s=p->next;（D）s->next=p;p->next=s;
38.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是（）。
（A）p=p-＞next;（B）p-＞next=p-＞next-＞next;（C）p-＞next=p;（D）p=p-＞next-＞next;
39.某线性表中最常用的操作是存取序号为i的元素及其前驱的值，可采用的存储的方式是（）。
（A）顺序表 （B）单向链表 （C）双向循环链表 （D）单向循环链表
40.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）。
（A）顺序表（B）用头指针表示的单循环链表（C）用尾指针表示的单循环链表（D）单链表
41.在单链表中，头结点是必不可少的。
（）
42.在单链表中，头结点的作用是简化运算。
（）
43.在线性表的顺序存储结构中，逻辑上相邻的数据元素在物理位置上也是相邻的。
（）
44.在线性表的链式存储结构中，逻辑上相邻的数据元素在物理位置上也是相邻的。
（）
45.只要内存足够大，采用链式存储结构的线性表长度不受限制。
（）
三、栈和队列
46.仅允许在表的一端进行插入与删除操作的线性表称作【】，允许在表的一端进行插入，另一端进行删除操作的线性表
称作【】。
47.栈称为【】线性表。
队称为【】线性表。
48.队列的操作是按【】的原则进行的。
49.栈的运算特点是【】。
请将用C语言的顺序栈的定义补充完整：
typedefstruct
{【】；
【】；
}seqstack；
50.以下运算实现在顺序栈上的进栈，请在空白处用适当的语句予以填充。
typedefstruct
{
DataTypedata[maxsize]；
inttop；
}SeqStack；
intPush（SeqStack*sq,DataTypex）
{if（sp->top==maxsize-1）{error（“栈满”）；return（0）；}
else{【】；
【】=x；
return
（1）；
}
}
51.队列的操作是按【】原则进行的。
循环队列Q分配Maxsize个存储单元，队头指针为front，队尾指针为rear，采用少用一个空间的方法处理，判断队列满的条件是【】。
52.循环队列是队列的【】存储结构。
53.循环队列Q分配Maxsize个存储单元，队头指针为front，队尾指针为rear，采用少用一个空间的方法处理，判断队列满的条件是【】。
54.以下顺序栈定义及出栈运算实现，请在空白处用适当语句填充。
typedefstruct
{
DataTypedata[maxsize]；
inttop；
}SeqStack；
intPop（SeqStack*sp，DataType*x）
{if（sp->top==0）
{error（“空栈”）；return（0）；}
else{*x=_______________；
_______________；
return
（1）；}
}
55.栈操作的原则是（）。
（A）先进先出 （B）后进先出 （C）栈顶插入 （D）栈顶删除
56.栈的两种常用存储结构分别为
（A）顺序存储结构和链式存储结构（B）顺序存储结构和散列存储结构
（C）链式存储结构和索引存储结构（D）链式存储结构和散列存储结构
57.有一栈，元素A，B，C，D依次进栈,则以下出栈序列中不可能得到的是（）。
（A）D、C、B、A（B）C、B、A、D（C）A、B、C、D（D）D、C、A、B
58.一个栈的入栈序列是A,B,C,D,E,则不可能的出栈序列是（）。
（A）EDCBA（B）DECBA（C）DCEAB（D）ABCDE
59.若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为
（A）4（B）5（C）6（D）7
60.循环队列是队列的（）。
（A）顺序存储结构（B）链式存储结构（C）索引存储结构（D）散列存储结构
61.设循环队列中数组的下标范围是1～n，其头尾指针分别是f、r，则队列中元素个数为（）。
（A）r-f （B）r–f+1（C）（r–f+1）modn （D）（r–f+n）modn
62.在循环队列中（少用一个存储空间），队满的条件是（）。
（A）（rear+1）%maxsize==front （B）raer==front
（C）（front+1）%maxsize==rear （D）rear==0
63.循环队列的队满条件为（）。
（A）（sq.rear+1）%mazsize==（sq.front+1）%maxsize;
（B）（sq.rear+1）%maxsize==sq.front+1
（C）sq.（rear+1）%maxsize==sq.front
（D）sq.rear==sq.front
64.设数组data[m]作为循环队列SQ的存储空间，front为头指针，rear为尾指针，执行出队操作,其头指针的值为（）。
（A）front=front+1（B）front=（front+1）%（m-1）（C）front=（front-1）%m（D）front=（front+1）%m
65.栈和队列与线性表的逻辑结构相同。
（）
66.栈只能在栈顶进行插入和删除。
（）
67.队列只能在队首进行删除，在队尾进行插入。
（）
68.队列只能在队尾进行删除，在队首进行插入。
（）
四、字符串，数组，广义表
69.通常采用【】存储结构来存放数组。
对二维数组可有两种存储方法：
一种是以【】为主序的存储方式，另一种是以【】为主序的存储方式。
70.已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC（a1），那么，LOC（ai）=【】。
71.在C语言中定义的二维数组intM[10][20]，每个元素（整数）占两个存储单元，数组的起始地址为2000，M[8][19]的存储值为【】。
元素M[5][10]的存储位置为【】。
72.假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。
已知A的基地址为1000，那么元素A[3，6]在按行存储时的地址是【】，按列存储时的地址是【】。
73.对称方阵采用压缩存储，即为每一对对称位置元素只分配一个存储空间，则可将n2个元素压缩存储到【】个元素的存储空间中。
74.有一个10阶对称矩阵A[10][10]，采用压缩存储方式以行序为主存储，A[0][0]的位置是1，则A[8][5]的位置是【】。
75.三元组表是【】的【】存储结构。
76.字符串S=“Computer”中，以p为首字符的子串有【】个。
77.TAIL[HEAD[（（a,b）,（c,d））]]运算的结果是【】。
78.广义表L=（（x,a）,（x,a,（b,c））,y）的长度是【】。
79.设广义表A=（a,b）,B=（c,d）,求head（（A,B））的值为【】。
80.有如下稀疏矩阵，请写出它的三元组表：
81.串是（）。
（A）一些符号构成的序列 （B）有限个字母构成的序列
（C）一个以上的字符构成的序列 （D）有限个字符构成的序列
82.已知函数Sub（s,i,j）的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy（s,t）的功能为复制串t到s。
若字符串S=“SCIENCESTUDY”，则调用函数Scopy（P,Sub（S,1,7）后得到（）。
（A）P=“SCIENCE”（B）P=“STUDY”（C）S=“SCIENCE”（D）S=“STUDY”
83.设有一个二维数组A[6][8],假设A[0][0]存放位置在1000,每个元素占6个空间，按行优先存储，则A[3][6]的存储位置是
（A）1180 （B）1126（C）126 （D）180
84.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第五个元素的地址是___________。
（A）110（B）108（C）100（D）120
85.为了节省存储空间，将n阶对称矩阵A（下标从1开始）中包括主对角线元素在内的下三角部分的所有元素按照行序为主序方式存放在一维数组B[1:
n（n+1）/2]中，对任意下三角部分的元素aij（i≥j）在数组B的下标k是___________。
（A）i（i-1）/2+j-1（B）i（i-1）/2+j（C）i（i+1）/2+j-1（D）i（i+1）/2+j
86.稀疏矩阵一般的压缩存储有两种，即（）。
（A）二维数组和三维数组（B）三元组表和哈希表（C）三元组表和十字链表（D）哈希表和十字链表
87.基于三元组的稀疏矩阵，对每个非零元素aij,可以用一个（）唯一确定。
（A）非零元素（B）三元组（i,j,aij）（C）aij（D）i,j
88.广义表A=（（）,（a）,（b,（c,（D）））的长度为___________。
（A）2 （B）3 （C）4 （D）5
89.空串与由空格组成的串没有区别。
（）
90.对称矩阵的压缩存储是指对矩阵中的值相同的元素只分配一个存储空间。
（）
91.对称矩阵的压缩存储是指对矩阵中的规律元素只分配一个存储空间。
（）
92.N阶下三角矩阵压缩存储需要n*（n+1）/2个存储空间。
（）
93.三元组表是稀疏矩阵的顺序存储结构。
（）
五、树型结构
94.在二叉树中，第i层的结点数最多为【】；
95.深度为k的二叉树的结点总数最多为【】。
96.对任何二叉树，若度为2的节点数为n2，则叶子数n0=【】。
97.在一棵完全二叉树中，若编号为i的结点有左孩子，则该左孩子结点的编号为【】；若编号为i的结点有右孩子，则该右孩子结点的编号为【】。
98.一棵深度为5的二叉树最多有【】个结点。
99.深度为h且有【】个结点的二叉树称为满二叉树。
（设根结点处在第1层）。
100.具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编号（根结点为1号），则编号最大的分支结点序号是【】，编号最小的分支结点序号是【】，编号最大的叶子结点序号是【】，编号最小的叶子结点序号是【】。
101.在有n个结点的二叉树，采用二叉链表存放，空链域的个数为【】。
102.二叉树通常有【】存储结构和【】存储结构两类存储结构。
103.给定二叉树的两种遍历序列，分别是：
前序遍历序列：
D，A，C，E，B，H，F，G，I；中序遍历序列：
D，C，B，E，H，A，G，I，F，试画出二叉树【】。
104.请对给定的二叉树的存储结构，将二叉树的中序遍历输出结点递归算法补充完整：
typedefstructnode
{chardata；/*元素为字符型*/
structnode*Lchild，*Rchild；
}BiTree；
voidInorder（BiTreeroot）
{if（root!
=NULL）
{【】；
【】；
【】；
}
}
105.请对给定的二叉树的存储结构，将二叉树的先序遍历输出结点递归算法补充完整：
typedefstructnode
{chardata;/*元素为字符型*/
structnode*Lchild,*Rchild;
}BiTree;
voidpreorder（BiTreeroot）
{if（root!
=NULL）
{【】;
【】;
【】;
}
}
106.以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。
voidcountleaf（bitree*t,int*count）/*根指针为t，假定叶子数count的初值为0*/
{if（t!
=NULL）
{if（（t->lchild==NULL）&&（t->rchild==NULL））【】;
countleaf（t->lchild,&count）;
【】
}
｝
107.哈夫曼树是带权路径长度【】的树，通常权值较大的结点离根【】。
108.有m个叶子结点的哈夫曼树，其结点总数为【】。
109.用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度是【】。
110.按照二叉树的定义，具有3个结点的二叉树有___________种形态。
（A）3（B）4（C）5（D）6
111.3个结点可构成（ ）个不同形态的二叉树。
（A）2 B3 C4 D5
112.二叉树是非线性数据结构，它（）。
（A）不能用顺序存储结构存储;（B）不能用链式存储结构存储;
（C）顺序存储结构和链式存储结构都能存储;（D）顺序存储结构和链式存储结构都不能使用
113.下列陈述中正确的是（）。
（A）二叉树是度为2的树（B）二叉树中结点只有一个孩子时无左右之分
（C）二叉树中必有度为2的结点（D）二叉树中最多只有两棵子树，并且有左右之分
114.设有一棵22个结点的完全二叉树，那么整棵二叉树有（）个度为0的结点?
（A）6（B）7（C）8（D）11
115.某非空二叉树共有叶结点15个，没有度为1的结点，则该树共有（）个结点。
（A）29 （B）28 （C）27 （D）不能确定
116.已知完全二叉树有26个结点，则整棵二叉树有（）个度为1的结点？
（A）1（B）0（C）2（D）不确定
117.将一棵有50个结点的完全二叉树编号，根结点为1，每层从左到右依次编号，则编号为49的结点的双亲结点的编号是（）。
（A）23（B）24（C）25（D）26
118.对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）方法实现编号。
（A）前序遍历（B）中序遍历（C）后序遍历（D）从根开始进行层次
升级会员 