数据结构试卷（一）
一、单选题（每题2 分，共20分）
1.栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
2.用链接方式存储的队列，在进行插入运算时( ).
A. 仅修改头指针
B. 头、尾指针都要修改
C. 仅修改尾指针
D.头、尾指针可能都要修改
3.以下数据结构中哪一个是非线性结构？( )
A. 队列
B. 栈
C. 线性表
D. 二叉树
4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在
676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
A．688 B．678 C．692 D．696
5.树最适合用来表示( )。
A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
6.二叉树的第k层的结点数最多为( ).
A．2k-1 B.2K+1 C.2K-1 D. 2k-1
7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二
分查找，则查找A［3］的比较序列的下标依次为( )
A. 1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为
A. O（1）
B. O（n）
C. O（1og2n）
D. O（n2）
9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）
=K %9作为散列函数，则散列地址为1的元素有（）个，
A．1 B．2 C．3 D．4
10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A.5
B.6
C.7
D.8
二、填空题（每空1分，共26分）
1.通常从四个方面评价算法的质量：_________、_________、_________和_________。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数
为__________个，树的深度为___________，树的度为_________。
4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式
为_______________________________。
5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指
针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。
6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点
分别有_______个和________个。
7.AOV网是一种___________________的图。
8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有
向完全图中，包含有________条边。
9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元
素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。
10. 向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度
___________。
11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序
过程的时间复杂度为________。
12. 在快速排序、堆排序、归并排序中，_________排序是稳定的。 三、计算题（每题 6 分，共24分）
1. 在如下数组A 中链接存储了一个线性表，表头指针为A [0].next ，试写出该线性表。 A 0 1 2 3 4 5 6 7
data 60 50 78 90 34 40 next 3 5 7
2
4
1
2. 请画出下图的邻接矩阵和邻接表。
3. 已知一个图的顶点集V 和边集E 分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,
(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 4. 画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。 四、阅读算法（每题7分，共14分）
1. 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）设链表表示的线性表为（a 1,a 2, …,a n
）,写出算法执行后的返回值所表示的线性表。
2. void ABC(BTNode * BT) {
if BT {
ABC (BT->left); ABC (BT->right); cout<
该算法的功能是： 五、算法填空（共8分）
二叉搜索树的查找——递归算法:
bool Find(BTreeNode* BST,ElemType& item)
{
if (BST==NULL)
return false; //查找失败
else {
if (item==BST->data){
item=BST->data;//查找成功
return ___________;}
else if(item
return Find(______________,item);
else return Find(_______________,item);
}//if
}
六、编写算法（共8分）
统计出单链表HL中结点的值等于给定值X的结点数。
int CountX(LNode* HL,ElemType x)
数据结构试卷（二）
一、选择题(24分)
1．下面关于线性表的叙述错误的是（）。
(A) 线性表采用顺序存储必须占用一片连续的存储空间
(B) 线性表采用链式存储不必占用一片连续的存储空间
(C) 线性表采用链式存储便于插入和删除操作的实现
(D) 线性表采用顺序存储便于插入和删除操作的实现
2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。
(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m
3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）。
(A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M
4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。
(A) BADC (B) BCDA (C) CDAB (D) CBDA
5．设某完全无向图中有n个顶点，则该完全无向图中有（）条边。
(A) n(n-1)/2 (B) n(n-1) (C) n2(D) n2-1
6．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。
(A) 9 (B) 10 (C) 11 (D) 12
7．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。
(A) n-1 (B) n (C) n+1 (D) 2n-1
8．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。
(A) 2，3，5，8，6 (B) 3，2，5，8，6
(C) 3，2，5，6，8 (D) 2，3，6，5，8
二、填空题(24分)
1.为了能有效地应用HASH查找技术，必须解决的两个问题是____________________和
__________________________。
2.下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。
typedef struct {int s[100]; int top;} sqstack;
void push(sqstack &stack,int x)
{
if (stack.top==m-1) printf(“overflow”);
else {____________________;_________________;}
}
3.中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。
4.快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。
5.设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为
2的结点数为_________；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。
6.设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=_______。
7.设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立
的初始堆为___________________________。
8．已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是
，BFS遍历的输出序列是
三、应用题(36分)
1．设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。
2．设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A 的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。3．设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。
4．设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。5．设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。
6．设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。
四、算法设计题(16分)
1．设有一组初始记录关键字序列（K1，K2，…，K n），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K i，右半部分的每个关键字均大于等于K i。
2．设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。
数据结构试卷（三）
一、选择题(每题1分，共20分)
1．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（）。
(A) 线性结构(B) 树型结构(C) 物理结构(D) 图型结构
2．下面程序的时间复杂为（）
for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；}
(A) O(n) (B) O(n2) (C) O(n3) (D) O(n4)
3．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。
(A) q=p->next；p->data=q->data；p->next=q->next；free(q)；
(B) q=p->next；q->data=p->data；p->next=q->next；free(q)；
(C) q=p->next；p->next=q->next；free(q)；
(D) q=p->next；p->data=q->data；free(q)；
4．设有n个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。
(A) 1 (B) n (C) nlog2n (D) n2
5．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )。
(A) 10，15，14，18，20，36，40，21
(B) 10，15，14，18，20，40，36，21
(C) 10，15，14，20，18，40，36，2l
(D) 15，10，14，18，20，36，40，21
6．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。
(A) n，e (B) e，n(C) 2n，e(D) n，2e
8. 设某强连通图中有n个顶点，则该强连通图中至少有（）条边。
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。
(A) 快速排序(B) 堆排序(C) 归并排序(D) 插入排序
10.下列四种排序中（）的空间复杂度最大。
(A) 插入排序(B) 冒泡排序(C) 堆排序(D) 归并排序
二、填空殖(每空1分共20分)
1.数据的物理结构主要包括_____________和______________两种情况。
2.设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作
为该完全二叉树的存储结构，则共有___________个空指针域。
3.设输入序列为1、2、3，则经过栈的作用后可以得到___________种不同的输出序列。
4.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和
等于顶点i的________，第i列上所有元素之和等于顶点i的________。
5.设哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。
6.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为
_________。
7.__________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或
后序）。
8.设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较
________次就可以断定数据元素X是否在查找表中。
9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为
____________。
10.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第
i个结点的双亲结点编号为____________，右孩子结点的编号为___________。
11.设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的
一趟快速排序结果为___________________________。
12.设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图
的一种拓扑序列为____________________。
13.下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。
struct record{int key; int others;};
int hashsqsearch(struct record hashtable[ ],int k)
{
int i,j; j=i=k % p;
while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);}
if (_______________________ ) return(j); else return(-1);
}
14.下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。
typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree;
bitree *bstsearch(bitree *t, int k)
{
if (t==0 ) return(0);else while (t!=0)
if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________;
}
三、计算题(每题10分，共30分)
1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。
2．已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试：
（1）计算出每一个元素的散列地址并在下图中填写出散列表：
` 0 1 2 3 4 5 6
（2）求出在查找每一个元素概率相等情况下的平均查找长度。
3．已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。
四、算法设计题(每题15分，共30分)
1．设计在单链表中删除值相同的多余结点的算法。
2．设计一个求结点x在二叉树中的双亲结点算法。
数据结构试卷（四）
一、选择题(每题1分共 20分)
1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。
(A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2)
2．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。
(A) 2k-1 (B) 2k(C) 2k-1(D) 2k-1
3．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。
(A) n (B) e (C) 2n (D) 2e
4．在二叉排序树中插入一个结点的时间复杂度为（）。
(A) O(1) (B) O(n) (C) O(log2n) (D) O(n2)
5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。
(A) n (B) n-1 (C) m (D) m-1
6．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。
(A) 3 (B) 4 (C) 5 (D) 8
7．设用链表作为栈的存储结构则退栈操作（）。
(A) 必须判别栈是否为满(B) 必须判别栈是否为空
(C) 判别栈元素的类型(D) 对栈不作任何判别
8．下列四种排序中（）的空间复杂度最大。
(A) 快速排序(B) 冒泡排序(C) 希尔排序(D) 堆
9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（）。
(A) N0=N1+1 (B) N0=N l+N2(C) N0=N2+1 (D) N0=2N1+l
10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不
超过（）。
(A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1)
二、填空题(每空1分共 20分)
1．设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。
2．设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。
3．根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____________。4．深度为k的完全二叉树中最少有____________个结点。
5．设初始记录关键字序列为(K1，K2，…，K n)，则用筛选法思想建堆必须从第______个元素开始进行筛选。
6．设哈夫曼树中共有99个结点，则该树中有_________个叶子结点；若采用二叉链表作为存储结构，则该树中有_____个空指针域。
7．设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储________个队列元素；当前实际存储________________个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。
8．设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_______个数据元素；删除第i个位置上的数据元素需要移动表中_______个元素。9．设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序结果为______________________________。
10．设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆为________________________。
11．设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j 互为邻接点的条件是______________________。
12．设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数_________第i列上非0元素的个数（填等于，大于或小于）。
13．设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_____________。
14．设散列函数H(k)=k mod p，解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。
typedef struct node {int key; struct node *next;} lklist;
void createlkhash(lklist *hashtable[ ])
{
int i,k; lklist *s;
for(i=0;i for(i=0;i { s=(lklist *)malloc(sizeof(lklist)); s->key=a[i]; k=a[i] % p; s->next=hashtable[k];_______________________; } } 三、计算题(每题10分，共30分) 1、画出广义表LS=(( ) , (e) , (a , (b , c , d )))的头尾链表存储结构。 2、下图所示的森林： (1) 求树（a）的先根序列和后根序列； (2) 求森林先序序列和中序序列； （3）将此森林转换为相应的二叉树； A B C D E F G H I J K (a)(b) 3、设散列表的地址范围是[ 0..9 ]，散列函数为H（key）= （key 2 +2）MOD 9,并采用链 表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。 四、算法设计题(每题10分，共30分) 1．设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。 2.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。 3.在链式存储结构上建立一棵二叉排序树。 数据结构试卷（五） 一、选择题(20分) 1．数据的最小单位是（）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（）。 (A) 40，50，20，95 (B) 15，40，60，20 (C) 15，20，40，45 (D) 45，40，15，20 3．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。 (A) 15，25，35，50，20，40，80，85，36，70 (B) 15，25，35，50，80，20，85，40，70，36 (C) 15，25，35，50，80，85，20，36，40，70 (D) 15，25，35，50，80，20，36，40，70，85 4．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。 (A) “STRUCTURE”(B) “DATA” (C) “ASTRUCTUR”(D) “DATASTRUCTURE” 5．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。 (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n) 6．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为N l，……，度数为m的结点数为Nm，则N0=（）。 (A) N l+N2+……+Nm (B) l+N2+2N3+3N4+……+(m-1)Nm (C) N2+2N3+3N4+……+(m-1)Nm (D) 2N l+3N2+……+(m+1)Nm 7．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 (A) 25 (B) 10 (C) 7 (D) 1 8．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（）。 (A) abedfc (B) acfebd (C) aebdfc (D) aedfcb 9．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（）。 (A) n-i (B) n-1-i (C) n+1-i (D) 不能确定 10 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45 为基准而得到一趟快速排序的结果是（）。 (A) 40，42，45，55，80，83 (B) 42，40，45，80，85，88 (C) 42，40，45，55，80，85 (D) 42，40，45，85，55，80 二、填空题(共20分) 1.设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶 指针top2的初值为n，则判断共享栈满的条件是____________________。 2.在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。 3.设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线 上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。 4.栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为 __________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。 5.设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历 序列为___________，中序遍历序列为___________，后序遍历序列为___________。6.设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________ 个叶子结点。 7.设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等 于顶点i的________，第i列中所有非零元素个数之和等于顶点i的__________。 8.设一组初始记录关键字序列(k1，k2，……，k n)是堆，则对i=1，2，…，n/2而言满足 的条件为_______________________________。 9.下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。 void bubble(int r[n]) { for(i=1;i<=n-1; i++) { for(exchange=0,j=0; j<_____________;j++) if (r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if (exchange==0) return； } } 10.下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。 struct record{int key; int others;}; int bisearch(struct record r[ ], int k) { int low=0,mid,high=n-1; while(low<=high) { ________________________________; if(r[mid].key==k) return(mid+1); else if(____________) high=mid-1;else low=mid+1; } return(0); } 三、应用题(32分) 1.设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC， 要求给出该二叉树的的后序遍历序列。 2.设无向图G（如右图所示），给出该图的最小生成树上边的集合并 计算最小生成树各边上的权值之和。 3.设一组初始记录关键字序列为(15，17，18，22，35，51，60)， 要求计算出成功查找时的平均查找长度。 4.设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(25，31，8，27， 13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。 四、算法设计题(28分) 1．设计判断两个二叉树是否相同的算法。2．设计两个有序单链表的合并排序算法。 数据结构试卷（六） 一、选择题(30分) 1．设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。 (A) 20 (B) 30 (C) 40 (D) 45 2．执行一趟快速排序能够得到的序列是（）。 (A) [41，12，34，45，27] 55 [72，63] (B) [45，34，12，41] 55 [72，63，27] (C) [63，12，34，45，27] 55 [41，72] (D) [12，27，45，41] 55 [34，63，72] 3．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。 (A) head==0 (B) head->next==0 (C) head->next==head (D) head!=0 4．时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（）。 (A) 堆排序(B) 冒泡排序(C) 希尔排序(D) 快速排序 5．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。 (A) 空或只有一个结点(B) 高度等于其结点数 (C) 任一结点无左孩子(D) 任一结点无右孩子 6．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（）。 (A) 堆排序(B) 冒泡排序(C) 快速排序(D) 希尔排序 7．设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。 (A) 3 (B) 4 (C) 5 (D) 6 8．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。 (A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n) 9．二路归并排序的时间复杂度为（）。 (A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n) 10. 深度为k的完全二叉树中最少有（）个结点。 (A) 2k-1-1 (B) 2k-1(C) 2k-1+1 (D) 2k-1 11.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针， 指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。 (A) front->next=s；front=s；(B) s->next=rear；rear=s； (C) rear->next=s；rear=s；(D) s->next=front；front=s； 12.设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。 (A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3) 13.设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。 (A) 99 (B) 100 (C) 101 (D) 102 14.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。 (A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n) 15.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。 (A) 第i行非0元素的个数之和(B) 第i列非0元素的个数之和 (C) 第i行0元素的个数之和(D) 第i列0元素的个数之和 二、判断题(20分) 1．调用一次深度优先遍历可以访问到图中的所有顶点。（） 2．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（） 3．冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（） 4．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（） 5．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（） 6．层次遍历初始堆可以得到一个有序的序列。（） 7．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（） 8．线性表的顺序存储结构比链式存储结构更好。（） 9．中序遍历二叉排序树可以得到一个有序的序列。（） 10.快速排序是排序算法中平均性能最好的一种排序。（） 三、填空题(30分) 1．for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为_________。 2．设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为__________________________（设结点的指针域为next）。 3．设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列__________。4．设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是_________。 5．设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_______个结点数。 6．设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_____________________。 7．设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是_____________________________________________。 8．简单选择排序和直接插入排序算法的平均时间复杂度为___________。 9．快速排序算法的空间复杂度平均情况下为__________，最坏的情况下为__________。10.散列表中解决冲突的两种方法是_____________和_____________。 四、算法设计题(20分) １．设计在顺序有序表中实现二分查找的算法。 ２．设计判断二叉树是否为二叉排序树的算法。 ３．在链式存储结构上设计直接插入排序算法 数据结构试卷（七） 一、选择题(30分) 1．设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。 (A) 2n (B) n (C) n/2 (D) n(n-1) 2．设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。 (A) n (B) n-1 (C) 2n (D) 2n-1 3．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是（）。 (A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80 (C) 42，40，55，60，80，85 (D) 42，40，60，85，55，80 4．（）二叉排序树可以得到一个从小到大的有序序列。 (A) 先序遍历(B) 中序遍历(C) 后序遍历(D) 层次遍历 5．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。 (A) 2i+1 (B) 2i (C) i/2 (D) 2i-1 6．程序段s=i=0；do {i=i+1；s=s+i；}while(i<=n)；的时间复杂度为（）。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2) 7．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。 (A) head==0 (B) head->next==0 (C) head->next==head (D) head!=0 8．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 (A) 20 (B) 256 (C) 512 (D) 1024 9．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。 (A) 1 (B) 2 (C) 3 (D) 4 10.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。 (A) top=top+1; (B) top=top-1; (C) top->next=top; (D) top=top->next; 二、判断题(20分) 1．不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（）2．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（） 3．设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（）4．完全二叉树中的叶子结点只可能在最后两层中出现。（） 5．哈夫曼树中没有度数为1的结点。（） 6．对连通图进行深度优先遍历可以访问到该图中的所有顶点。（） 7．先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（） 8．由树转化成二叉树，该二叉树的右子树不一定为空。（） 9．线性表中的所有元素都有一个前驱元素和后继元素。（） 10.带权无向图的最小生成树是唯一的。（） 三、填空题(30分) 1.设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A 的后面插入结点X的操作序列为_________=p；s->right=p->right；__________=s； p->right->left=s；（设结点中的两个指针域分别为left和right）。 2.设完全有向图中有n个顶点，则该完全有向图中共有________条有向条；设完全无向图 中有n个顶点，则该完全无向图中共有________条无向边。 3.设关键字序列为(K l，K2，…，K n)，则用筛选法建初始堆必须从第______个元素开始进 行筛选。 4.解决散列表冲突的两种方法是________________和__________________。 5.设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为 3的结点数有______个。 6.高度为h的完全二叉树中最少有________个结点，最多有________个结点。 7.设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后 的结果的是__________________________________。 8.设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟简单选择排序结束后 的结果的是__________________________________。 9.设一棵二叉树的前序序列为ABC，则有______________种不同的二叉树可以得到这种序 列。 10.下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。 struct record {int key;datatype others;}; void quickpass(struct record r[], int s, int t, int &i) { int j=t; struct record x=r[s]; i=s; while(i { while (i while (____________________) i=i+1; if (i } _________________; } 四、算法设计题(20分) 1.设计在链式结构上实现简单选择排序算法。 2.设计在顺序存储结构上实现求子串算法。 3.设计求结点在二叉排序树中层次的算法。 数据结构试卷（八） 一、选择题(30分) 1.字符串的长度是指（）。 (A) 串中不同字符的个数(B) 串中不同字母的个数 (C) 串中所含字符的个数(D) 串中不同数字的个数 2.建立一个长度为n的有序单链表的时间复杂度为（） (A) O(n) (B) O(1) (C) O(n2) (D) O(log2n) 3.两个字符串相等的充要条件是（）。 (A) 两个字符串的长度相等(B) 两个字符串中对应位置上的字符相等 (C) 同时具备(A)和(B)两个条件(D) 以上答案都不对 4.设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（）。 (A) 99 (B) 97 (C) 91 (D) 93 5.在二叉排序树中插入一个关键字值的平均时间复杂度为（）。 (A) O(n) (B) O(1og2n) (C) O(nlog2n) (D) O(n2) 6.设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较 元素的顺序为( )。 (A) A[1]，A[2]，A[3]，A[4] (B) A[1]，A[14]，A[7]，A[4] (C) A[7]，A[3]，A[5]，A[4] (D) A[7]，A[5] ，A[3]，A[4] 7.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。 (A) 8 (B) 7 (C) 6 (D) 5 8.设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点， 则该三叉链权中有（）个度数为0的结点。 (A) 5 (B) 6 (C) 7 (D) 8 9.设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}， 则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。 (A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc 10.队列是一种（）的线性表。 (A) 先进先出(B) 先进后出(C) 只能插入(D) 只能删除 二、判断题(20分) 1.如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（） 2.设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（） 3.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块 号，然后再在相应的块内进行顺序查找。（） 4.二维数组和多维数组均不是特殊的线性结构。（） 5.向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（） 6.如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（） 7.非空的双向循环链表中任何结点的前驱指针均不为空。（） 8.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为 O(n)。（） 9.图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问 过。（） 10.稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（） 三、填空题(30分) 1．设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为_____________________________。 2．下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。 typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree; void bstinsert(bitree *&t,int k) { if (t==0 ) {____________________________;t->data=k;t->lchild=t->rchild=0;} else if (t->data>k) bstinsert(t->lchild,k);else__________________________; } 3．设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next; _________________;。 4．设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_________和head=__________（设结点中的两个指针域分别为llink和rlink）。 5．设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为__________。 6．完全二叉树中第5层上最少有__________个结点，最多有_________个结点。 7．设有向图中不存在有向边 8．设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择排序结束后的结果为_____________________________。 9．设连通图G中有n个顶点e条边，则对应的最小生成树上有___________条边。 10．设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16与___________相互交换即可。 四、算法设计题(20分) 1.设计一个在链式存储结构上统计二叉树中结点个数的算法。 2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。 数据结构试卷（九） 一、选择题(30分) 1．下列程序段的时间复杂度为（）。 for(i=0；i for(i=0；i (A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n) 2．设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。 (A) n-i (B) n+l -i (C) n-1-i (D) i 3．设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（）。 (A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N3 4．利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n) 5．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）。 (A) p->right=s；s->left=p；p->right->left=s；s->right=p->right； (B) s->left=p；s->right=p->right；p->right=s；p->right->left=s； (C) p->right=s；p->right->left=s；s->left=p；s->right=p->right； (D) s->left=p；s->right=p->right；p->right->left=s；p->right=s； 6．下列各种排序算法中平均时间复杂度为O(n2)是（）。 (A) 快速排序(B) 堆排序(C) 归并排序(D) 冒泡排序 7．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。 (A) n-i (B) n-1-i (C) n+l -i (D) 不能确定 8．设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（）。 (A) 小于等于m的最大奇数(B) 小于等于m的最大素数 (C) 小于等于m的最大偶数(D) 小于等于m的最大合数 9．设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（）个。 (A) 4 (B) 5 (C) 6 (D) 7 10.设完全无向图中有n个顶点，则该完全无向图中有（）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2 11.设顺序表的长度为n，则顺序查找的平均比较次数为（）。 (A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2 12.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24 的元素需要经过（）次比较。 (A) 1 (B) 2 (C) 3 (D) 4 13.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查 找长度为（）。 (A) 6 (B) 11 (C) 5 (D) 6.5 14.设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于 该有向图G的一种拓扑排序序列的是（）。 (A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3 算法与数据结构复习资料 一、单选题 在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( B)。 A. HL=p;p->next=HL; B.p->next=HL->next;HL->next=p; C.p->next=HL;p=HL; D.p->next=HL;HL=p; 若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（B）个元素. A. n B.n-1 C.n+1 D.不确定 下述哪一条是顺序存储方式的优点？（A） A．存储密度大B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快 设有一个二维数组A[m][n]，假设A[0][0]存放位置在600 (10)，A[3][3]存放位置在678 (10) ， 每个元素占一个空间，问A[2][3] (10)存放在什么位置？(脚注 (10) 表示用10进制表示,m>3)C A．658 B．648 C．633 D．653 下列关于二叉树遍历的叙述中，正确的是( D) 。 A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点 B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点 D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点 k层二叉树的结点总数最多为(A). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 对线性表进行二分法查找，其前提条件是( C). A.线性表以链接方式存储，并且按关键码值排好序 B.线性表以顺序方式存储，并且按关键码值的检索频率排好序 C. 线性表以顺序方式存储，并且按关键码值排好序 D. 线性表以链接方式存储，并且按关键码值的检索频率排好序 对n个记录进行堆排序，所需要的辅助存储空间为（C） A. O（1og2n） B. O（n） C. O（1） D.O（n2） 对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有（D）个， A．1 B．2 C．3 D．4 下列关于数据结构的叙述中，正确的是( D). A. 数组是不同类型值的集合 B. 递归算法的程序结构比迭代算法的程序结构更为精炼 C. 树是一种线性结构 D. 用一维数组存储一棵完全二叉树是有效的存储方法 在决定选取何种存储结构时，一般不考虑（ A ）。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（B）。A．单链表B．静态链表C．线性链表D．顺序存储结构 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（A）。 A．q=p->next；p->data=q->data；p->next=q->next；free(q)； B．q=p->next；q->data=p->data；p->next=q->next；free(q)； C．q=p->next；p->next=q->next；free(q)； 第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题 （1）在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 （2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A．存储结构B．存储实现 C．逻辑结构D．运算实现 （3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 A．数据具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 （5）以下与数据的存储结构无关的术语是（）。 A．顺序队列B.链表C.有序表D.链栈 （6）以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90;y=100; while(y>0) if(x>100) {x=x-10;y--;} elsex++; （2）for(i=0;i 数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满 数据结构复习题 第一章概论 一、选择题 1、研究数据结构就是研究( D )。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是( A )。 A. 空间复杂度和时间复杂度 B. 正确性和简单性C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 fori0;im;i++ forj0;jn;j++ a[i][j]i*j; A. Om2 B. On2 C. Om*n D. Om+n 6、算法是( D )。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。 A. On B. Onlog2n C. On2 D. Olog2n 8、下面程序段的时间复杂度为( C )。 i1; whilein ii*3; A. On B. O3n C. Olog3n D. On3 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( B )和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是( A )。 is0; whilesn i++;s+i; A. On B. On2 C. Olog2n D. On3 11、抽象数据类型的三个组成部分分别为( A )。 A. 数据对象、数据关系和基本操作 B. 数据元素、逻辑结构和存储结构 C. 数据项、数据元素和数据类型 D. 数据元素、数据结构和数据类型 12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是(D)。 数据结构试卷（一） 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数 为__________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式 为_______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 7.AOV网是一种___________________的图。 8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中，包含有________条边。 9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 习 9解答 判断题： 1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 答：FALSE (错。链表表示的有序表不能用折半查找法。) 2.有n 个数据放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无序其平均查找长度不同。 答：FALSE (错。因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL 相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL 要比有序表的ASL 小。) 3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( ) 答：TRUE 4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。 答：TRUE 5.查找表是由同一类型的数据元素(或记录)构成的集合。 答：TRUE 单选题： 6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。 A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3 答：D (第一次??2/)181(+ = 9,第二次??2/)81(+ = 4，第三次??2/)31(+ = 2, (第四次??2/)33(+ = 3，故选D. 7. 顺序查找法适合于存储结构为____________的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 答：B 8.对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B. 以链接方式存储 C ．以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 答：C 9.设哈希表长m=14，哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图 数据结构辅导试题一 一、简答问题： 1．四类数据结构 2．线性结构与非线性结构有何差别？ 3．简述算法的定义与特性。 4．设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？ 二、判断正误：（每小题1分，共5分）正确在（）内打√，否则打 。1．（）二叉排序树或是一棵空树，或是具有下列性质的二叉树： 若它的左子树非空，则根结点的值大于其左孩子的值， 若它的右子树非空，则根结点的值大于其右孩子的值。 2．（）索引顺序表的特点是块内可无序，块间要有序。 3．（）子串是主串中任意个连续字符组成的序列。 4．（）线性结构只能用顺序结构存放，非线性结构只能用链表存放。 5．（）快速排序的枢轴元素可以任意选定。 三、单项选择题：(每小题1分，共4分) 1．栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列? A)E、D、C、B、A、F B)B、C、E、F、A、D C)C、B、E、D、A、F D)A、D、F、E、B、C 2．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为： A、98 B、99 C、50 D、48 3. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是： A）{21、25、5、17、9、23、30} B）{25、23、30、17、21、5、9} B）{21、9、17、30、25、23、5} D）{5、9、17、21、23、25、30} 4. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是： A）M1 B）M1+M2 C）M3 D）M2+M3 四、填空题：(每小题2分,共 20分) 1．设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P<=M）, 为使函数具有较好性能，P应选 2．N个结点的二叉树采用二叉链表存放，共有空链域个数为 3．单链表与多重链表的区别是 4．在各种查找方法中，平均查找长度与结点个数无关的是 5．深度为6（根层次为1）的二叉树至多有个结点。 6．已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是 7．在一个单链表中p所指结点之后插入s所指结点时,应执行 s->next= 和p->next= 的操作. 8．广义表((a,b),c,d)的表头是 ,表尾是 9．循环单链表LA中，指针P所指结点为表尾结点的条件是 10．在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，则使用排序方法最好。 五、构造题：（每小题5分，共25分） 1．已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。 2．设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散列或链 《算法与数据结构》习题1 第一部分 一、单项选择题 1.（）二叉排序树可以得到一个从小到大的有序序列。 A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 2.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i 结点的左孩子结点的编号为（）。 A、2i+1 B、2i C、i/2 D、2i-1 3.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序 列为（）。 A、q=p->next；p->data=q->data；p->next=q->next；free(q)； B、q=p->next；q->data=p->data；p->next=q->next；free(q)； C、q=p->next；p->next=q->next；free(q)； D、q=p->next；p->data=q->data；free(q)； 4.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得 到序列为（）。 A、BADC B、BCDA C、CDAB D、CBDA 5.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。 A、n B、n-1 C、m D、m-1 6.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。 A、O(1) B、O(log2n) C、O(nlog2n) D、O(n2) 7.设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A、25 B、10 C、7 D、1 二、填空题 1.设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A 的后面插入结点X的操作序列为______=p；s->right=p->right；______=s； p->right->left=s；（设结点中的两个指针域分别为left和right）。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为______。 3.设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为 3的结点数有______个。 4.后缀算式9 2 3 + - 10 2 / -的值为______。中缀算式（3+4X）-2Y/3对应的后缀算式 为______。 5.设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从第______个元 素开始进行筛选。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 复习题集─参考答案 一判断题 （√）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （√）2. 抽象数据类型与计算机部表示和实现无关。 （×）3. 线性表采用链式存储结构时，结点和结点部的存储空间可以是不连续的。 （×）4. 链表的每个结点中都恰好包含一个指针。 （×）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（×）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （×）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （×）8. 线性表在物理存储空间中也一定是连续的。 （×）9. 顺序存储方式只能用于存储线性结构。 （√）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （√）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）13.两个栈共享一片连续存空间时，为提高存利用率，减少溢出机会，应把两个栈的栈底分别设在这片存空间的两端。 （×）14.二叉树的度为2。 （√）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）16.二叉树中每个结点的两棵子树的高度差等于1。 （√）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）18.具有12个结点的完全二叉树有5个度为2的结点。 （√）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 （×）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。 （×）21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据] （×）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 （×）23.算法必须用程序语言来书写。 （×）24.判断某个算法是否容易阅读是算法分析的任务之一。 （×）25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] （√）26.分配给顺序表的存单元地址必须是连续的。 （√）27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表] （√）28.树形结构中每个结点至多有一个前驱。 （×）29.在树形结构中，处于同一层上的各结点之间都存在兄弟关系。 （×）30.如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。 （×）31.如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。 （×）32.顺序查找方法只能在顺序存储结构上进行。 （×）33.折半查找可以在有序的双向链表上进行。 数据结构模拟试题... 一、简答题（15分，每小题3分） 1.简要说明算法与程序的区别。 2.在哈希表中，发生冲突的可能性与哪些因素有关？为什么？ 3.说明在图的遍历中，设置访问标志数组的作用。 4.说明以下三个概念的关系：头指针，头结点，首元素结点。 5.在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？ 二、判断题（10分，每小题1分） 正确在括号内打√，错误打× ( )（1）广义表((( a ), b), c ) 的表头是(( a ), b)，表尾是( c )。 ( )（2）在哈夫曼树中，权值最小的结点离根结点最近。 ( )（3）基数排序是高位优先排序法。 ( )（4）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。 ( )（5）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p->next = s; s->next = p->next; ( )（6）抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。 ( )（7）数组元素的下标值越大，存取时间越长。 ( )（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。 ( )（9）拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。 ( )（10）长度为1的串等价于一个字符型常量。 三、单项选择题（10分, 每小题1分） 1．排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？ A、堆排序 B、直接插入排序 C、快速排序 D、冒泡排序 2．已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该： A）将邻接矩阵的第i行删除B）将邻接矩阵的第i行元素全部置为0 C）将邻接矩阵的第i列删除D）将邻接矩阵的第i列元素全部置为0 3．有一个含头结点的双向循环链表，头指针为head, 则其为空的条件是： A.head->priro==NULL B. head->next==NULL C. head->next==head D. head->next-> priro==NULL 4. 在顺序表( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比 数据结构与算法基础 一．判断题： 1．数据元素是数据的最小单位。 2．数据结构是带有结构的数据元素的集合。 3．数据结构、数据元素、数据项在计算机中的映像（或表示）分别称为存储结构、结点、数据域。 4．数据项是数据的基本单位。 5．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的。 6．数据的物理结构是指数据在计算机内实际的存储形式。 7．算法和程序没有区别，所以在数据结构中二者是通用的。 答案： 1．错误 2．正确 3．正确 4．错误 5．正确 6．正确 7．错误 二． 数据结构是研究数据的 A 和 B 以及它们之间的相互关系，并对这种结构定义相应的 C ，设计出相应的 D ，而确保经过这些运算后所得到的新结构是 E 结构类型。 供选择答案： A、Ｂ：ａ理想结构ｂ抽象结构ｃ物理结构ｄ逻辑结构 Ｃ、Ｄ、Ｅ：ａ运算ｂ算法ｃ结构ｄ规则ｅ现在的ｆ原来的 答案： Ａ：ｃＢ；ｄＣ：ａＤ：ｂＥ：ｆ 三．从供选择的答案中选取正确的答案填在下面叙述中的横线上： 1． A 是描述客观事物的数字、字符以及所能输入到计算机中并被计算机程序加工处理的符号的集合。 2. B 是数据的基本单位,即数据集合中的个体。有时一个 B 由若干个___C____组成，在这种情况下，称 B 为记录。 C 是数据的最小单位。而由记录所组成的线性表为 D 。 3. E 是具有相同特性的数据元素的集合，是数据的子集。 4. Ｆ是带有结构特性数据元素的集合。 5. 被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系。通常将数据元素的这种关系称为Ｇ。 6. 算法的计算量的大小称为计算的Ｈ。 供选择的答案： Ａ－Ｆ：ａ数据元素ｂ符号ｃ记录ｄ文件ｅ数据ｆ数据项ｇ数据对象ｈ关键字ｉ数据结构 《算法与数据结构》习题1 一、单项选择题 1. 数据结构从逻辑上分为（）。 A．动态结构和静态结构 B．内部结构和外部结构 C．紧凑结构和非紧凑结构 D．线性结构和非线性结构 2. 栈和队列的共同点是（）。 A．都是先进后出 B．都是后进先出 C．只允许在端点处插入和删除元素 D．没有共同点 3．若按从左到右的顺序读入已知序列a、b、c、d、e、f、g中的元素，然后结合栈的操作，能得到下列序列中的哪些序列？（） A．decfbga B．fegdacb C．efdgbca D．dcbefag 4. 在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点 s，则执行（）。 A．s→link=p→link；p→link =s； B．p→link =s；s→link=q； C．p→link=s→link；s→link =p； D．q→link =s；s→link=p； 5．算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 6. 一个算法应该是（）。 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C 7. 从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8. 以下数据结构中，哪一个是线性结构？（） A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 二、多项选择题 1. 以下说法正确的是（）。 A. 二叉树的特点是每个结点至多只有两棵子树 B. 二叉树的子树无左右之分 C. 二叉树只能进行链式存储 D. 树的结点包含一个数据元素及若干指向其子树的分支2．在数组上能做的操作有（）。 A.插入 B.删除 C.取值操作 D.赋值操作 3. 图的应用算法有（）。 A. 克鲁斯卡尔算法 B. 哈弗曼算法 C. 迪杰斯特拉算法 D. 拓扑排序算法 4. 计算机算法必须具备（）等特性。 A. 可行性、确定性 B. 可行性、可移植性 C. 输入、输出 《数据结构》 Part1 一．选择 1. 组成数据的基本单位是（） A）数据项B）数据类型C）数据元素D）数据变量 2．算法分析的目的是（） A）找出数据结构的合理性B）研究算法的输入/输出关系 C）分析算法的效率以求改进D）分析算法的易读性 3．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）A）O(1) B）0(n) C）O(n^2) D）O(nlog2n) 4．若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址是（） A）112 B）144 C）148 D）412 5．下面关于线性表的叙述中，错误的是（） A）顺序表使用一维数组实现的线性表B）顺序表必须占用一片连续的存储单元. C）顺序表的空间利用率高于链表D）在单链表中,每个结点只有一个链域. 6．在需要经常查找结点的前驱与后继的情况下，使用（）比较合适 A）单链表B）双链表C）顺序表D）循环链表 7．队列通常采用的两种存储结构是（） A）顺序存储结构和链式存储结构B）散列方式和索引方式 C）链表存储结构和线性存储结构D）线性存储结构和非线性存储结构 8．在一个单链表中，若删除p所指结点的后继结点，则执行（） A）p->next=p->next->next；B）p=p->next；p->nex=p->next->next； C）p->next=p->next；D）p=p->next->next； 9．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间 A）单链表B）仅有头指针的单循环链表C）双链表D）仅有尾指针的单循环链表 10．按二叉树的定义，具有三个结点的二元树共有（）种形态。 A）3 B）4 C）5 D）6 11．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）A）发生改变B）不发生改变C）不能确定D）以上都不对12．深度为5的二叉树至多有（）个结点 A）16 B）32 C）31 D）10 13．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（）个。 A）4 B）5 C）6 D）7 14．对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组(顶点表)的大小为（） A）n B）n+1 C）n-1 D）n/2 15．静态查找表和动态查找表二者的根本差别在于（） 考点1 算法的复杂度 【考点精讲】 1．算法的基本概念 计算机算法为计算机解题的过程实际上是在实施某种算法。 算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。 2．算法复杂度 算法复杂度包括时间复杂度和空间复杂度。 名称 描述 时间复杂度 是指执行算法所需要的计算工作量 空间复杂度 是指执行这个算法所需要的内存空间 考点2 逻辑结构和存储结构 【考点精讲】 1．逻辑结构 数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。一个数据结构可以表示成 B=（D，R） 其中B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。例如，如果把一年四季看作一个数据结构，则可表示成 B =（D,R） D ={春季，夏季，秋季，冬季} R ={（春季，夏季）,（夏季，秋季），（秋季，冬季）} 2．存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。 由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。 一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接等存 储结构。 顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。 链式存储结构就是在每个结点中至少包含一个指针域，用指针来体现数据元素之间逻辑上的联系。 考点3 线性结构和非线性结构 【考点精讲】 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。栈、队列、串等都线性结构。 如果一个数据结构不是线性结构，则称之为非线性结构。数组、广义表、树和图等数据结构都是非线性结构。 考点4 栈 【考点精讲】 1．栈的基本概念 栈（stack）是一种特殊的线性表，是限定只在一端进行插入与删除的线性表。在栈中，一端是封闭的，既不允许进行插入元素，也不允许删除元素；另一端是开口的，允许插入和删除元素。通常称插入、删除的这一端为栈顶，另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。 栈是按照“先进后出”或“后进先出”的原则组织数据的。例如，枪械的子弹匣就可以用来形象的表示栈结构。子弹匣的一端是完全封闭的，最后被压入弹匣的子弹总是最先被弹出，而最先被压入的子弹最后才能被弹出。 2．栈的顺序存储及其运算 栈的基本运算有三种：入栈、退栈与读栈顶元素。 （1）入栈运算：入栈运算是指在栈顶位置插入一个新元素。 （2）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。 （3）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。 考点5 队列 【考点精讲】 1．队列的基本概念 队列是只允许在一端进行删除，在另一端进行插入的顺序表，通常将允许删除的这一端称为队头，允许插入的这一端称为队尾。 当表中没有元素时称为空队列。 队列的修改是依照先进先出的原则进行的，因此队列也称为先进先出的线性表，或者后进后出的线性表。例如：火车进遂道，最先进遂道的是火车头，最后是火车尾，而火车出遂道的时候也是火车头先出，最后出的是火车尾。若有队列： Q =（q1，q2，…，qn） 那么，q1为队头元素（排头元素），qn为队尾元素。队列中的元素是按照q1，q2，…，qn 的顺序进入的，退出队列也只能按照这个次序依次退出，即只有在q1，q2，…，qn-1 都退队之后，qn才能退出队列。因最先进入队列的元素将最先出队，所以队列具有先进先出的 数据结构与算法试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为 (C ) A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时,要求占用的存储空间地址(D ) A 必须就是连续的 B 部分地址必须就是连续的 C 一定就是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为( D )。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中,若q结点就是p结点的前驱结点,若在q与p之间插入结点s,则执行( D )。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个,采用( C )方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t与p,求p在t中首次出现的位置的运算叫做( B )。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中,每一个数组元素A[i][j]占用3个存储字,行下标i从1到8,列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中,则存放该数 组至少需要的存储字数就是( C )。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时,通常需要使用( A )。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序就是1, 2, 3, 4,则出队列顺序为( C )。 10、在循环队列中用数组A[0、、m-1] 存放队列元素,其队头与队尾指针分别为front与rear,则当前队列中的元素个数就是( D )。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与( A )的表示等价。 A *(a+i) B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参,则应把形参变量说明为( B )参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为( C ) for (int i=0;i 数据结构与算法考试参考题 专业：计算机科学与技术 13年 一、单选（ 30分） 1. 在数据结构中，数据的逻辑结构可分（ B.线性结构和非线性结构） 2. 在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ C.指向后继元素的指针表示） 3.设p指向单链表中的一个结点。S指向待插入的结点，则下述程序段的功能是（ D.在结点*p之前插入结点*s ） s->next=p->next; p->next=s! t=p->data; p->data=s->data; s->data=t; B.在p所指结点的元素之前插入元素 D.在结点*p之前插入结点*s 4. 栈和队列都是（ C:链式存储的线性结构） A:限制存取位置的线性结构 B:顺序存储的线性结构 C:链式存储的线性结构D:限制存取位置的非线性结构 5.下列关于线性表的基本操作中，属于加工型的操作是（ B初始化、插入、删除操作） 6. 根据定义，树的叶子结点其度数（ B.必等于0 ） 7. 多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（ A.数组的元素处在行和列两个关系中） 8. 从广义表LS=（（ p,q ）,r,s ）中分解出原子q的运算是(B. head(tall(head (LS))) 9. 在具有n个叶子结点的满二叉树中，结点总数为（ C. 2n-1 ） 10. 若算法与数据结构复习资料
数据结构与算法习题及答案
数据结构与算法基础知识总结
数据结构与算法复习题库含答案
算法与数据结构试题及答案
数据结构与算法复习题10(C语言版)
大数据结构考试精彩试题
算法与数据结构习题
数据结构与算法复习题及参考答案
算法与数据结构试题及答案
数据结构与算法基础
算法与数据结构练习题
数据结构和C++程序设计_题库
全国计算机二级第1章数据结构与算法
数据结构与算法试题
数据结构及算法_考试范围题及答案解析like
相关主题
文本预览