2011datastructure习题

题1.1

数据结构在计算机内存中的表示是指———。 A．数据的存储结构 B．数据元素

C．数据的逻辑结构 D．数据元素之间的关系 题1.2

从逻辑上可把数据结构分为——。

A.动态结构和静态结构 B.顺序结构和链式结构 C.线性结构和非线性存储结构 D.内部结构和外部结构 题1.3

判断正误：数据元素是数据的最小单位。 题1.4

分析下列程序段的时间复杂度： (1) x=1;

for (i=1;i<=n;i++)

for (j=1;j<=i;j++)

for (k=1;k<=j;k++)

x++;

(2) for (i=1;i

for (j=0; j<=(2*n); j++)

x++;

}

(3) i=1; while (i<=n) i=i*2 (4) i=0; s=0; while(s

{ i=i+1; s=s+i; }

题1.5

设n是偶数，试计算运行下列程序段后m的地址并给出该程序段的时间复杂度。 m=0；

for(i=1;i<=n;i++) for(j=2*i;j<=n;j++) m=m+1;

题2.1

线性表的静态链表存储结构与顺序存储结构相比优点是——。 A．所有的操作算法实现简单 B．便于随机存取 C. 便了插入和删除 D．便于利用零散的存储器空间 题2.2 判断正误

? 1.顺序存储只能用于存储线性结构

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

题2.3

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

? 线性链表中各链接点的位置——。 A．必须连续 B．部分地址必须连续 C. 不一定连续 D．连续与否无所谓

题2.5

? 线性表是具有n个（ ）的有限序列。

(1)表元素 (2)字符 (3)数据元素 (4)数据项 (5)信息项

题2.6

若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个元素的时间复杂度为（1<= i <= n+1 ）。

A.O(0) B.O(1) C.O(n) D.O(n2) 题2.7

? 表长为n的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个

元素需移动元素的平均个数 ，删除一个元素需移动元素的平均个

数 。

题2.8

? 已知结点指针p、q分别表示双向链表中任意两个相邻结点(即p->next=q，

q->prior=p)，请写出删除q所指向结点的程序段。

题2.9

? 将两个各有n个元素的有序表归并成一个有序表，其最小的比较次数

是 。 A.n B.2n-1 C.2n D.n-1 题2.10

? 填空：在一个单链表的p结点之前插入一个人结点s时，可执行如下操作： (1)s->next = ; (2)p->next = s; (3)t = p->data;

(4)p->data = ; (5)s->data = ; 题2.11

? 带头结点的双向循环链表L为空表的条件是 。 题2.12

? 需要分配较大存储空间，插入和删除不需要移动元素的线性表，其存储结构

是 。 A.单链表 B.静态链表 C.线性链表 D.顺序存储结构 题2.13

? 有一个单链表L，其结点的元素值以非递减有序排列，编写算法删除该单链表中多

余的元素值相同的结点。

题2.14

? 有一个单链表L(至少有一个结点)，其头结点指针为L，编写一个过程将L置逆，要

求逆转在原链表上进行

题3.1

若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列删除一个元素，再加入两个元素后，rear和front的值分别为 。 A.1和5 B.2和4 C.4和2 D.5和1

题3.2

? 用数组表示的循环队列的队首位置和队尾位置分别为1和max_size，试给出判断队

列为空和满的条件(队列长度最大为MAXSIZE)。 题3.3

若某堆栈的输入序列为1,2,3,…,n，输出序列的第一个元素为n，则第i个输出元素为 。

A.i B.n-i C. n-i+1 D.哪个元素无所谓 题3.4

设栈的输入序列是1,2,3,4，则 不可能是其出栈顺序。 A. 1243 B.2134 C.1432 D.4312 E.3214

题3.5

设输入元素为1、2、3、P和A，输入次序为123PA。元素经过栈后到达输出序列，当所有元素都到达输出序列后，有哪些序列可作为高级语言的变量名。

题3.6

设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b、d、c、f、e、a，则栈的容量至少为？ 题3.7

用数组Q(其下标在0…n-1，共有n个元素)表示一个循环队列，f为当前对头元素的前一位置，r为队尾元素位置，假定队列中元素个数总小于n，求队列中元素个数的公式是 。

题4.1

? 是C语言中“abcd321ABCD”的子串。

A．abcd B．321AB C. “abcABC” D．“21AB”

题4.2

? 字符串满足为下式，其中Head和Tail的定义与广义表类似，则S= 。

? Contact(Head(Tail(S)), Head(Tail(Tail(S)))) = “dc”

? A. abcd B.acbd C.acdb D.adcb 题4.3

设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非空子串(不含S本身)的个数是 。

A.2n-1 B.n2 C.(n2/2)+(n/2) D.(n2/2)+(n/2)-1 E.(n2/2)+(n/2)+1

题4.4

? 若串S = “software”，其非空子串数目为（ ）。 A．8 B．37 C. 36 D．9

题4.5

? 填空：两个串相等的充分必要条件是 。 题4.6

? 空串和空格串的区别是？

题5.1

? 填空：设有上三角矩阵A(aij)n*n，将其上三角元素逐行存于数组B[1…m]中(m充分

大)，使得B[k]=aij，则k= 。 题5.2

数组a中，每个元素a[i, j]的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址连续存放在存储器内，该数组按行优先存放时，元素a[7][4]的起始地址为 . A.a+141 B.a+144 C.a+222 D.a+225

题5.3

填空：已知10行20列的二维数组A按行优先方式存放，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[5][11]的地址是 ；如果该数组按列优先方式存放，则A[5][11]的地址是 。

题5.4

? 填空：有一个10阶对称矩阵A，采用压缩存储方式(以行序位主序且A[0][0]地址为

1)，则A[7][4]的地址为 。 题5.5

? 填空：将一个A[0..99, 0..99]的三对角矩阵，按行优先存入一维数组B[0..297]中，A

中元素A[65][64]在B中的位置k为 。

题5.6

? 若广义表A满足Head(A) = Tail(A)，则A为 。

? A.( ) B.(( )) C.(( ), ( )) D.(( ), ( ), ( ))

题5.7

? 设广义表L = (( ), ( ))，则Head( L)= ，Tail( L)= ，L的长度

是 ，L的深度是 。 题6.1

? 设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所包含的结点数

至少为 ，至多为 。

A.2h B.2h-1 C.2h+1 D.h+1

E.2h-1 F.2h-1 G.2h+1 H.2h+1+1 题6.2

? 某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，画出该二叉树，

并求其后序遍历序列。

题6.3

若一个具有n个顶点，k条边的无向图是一个森林(N>K),则该森林中必有 颗树。 A.k B.n C.n-k D. 1

题6.4

? 填空：深度为k的完全二叉树至少有 个结点， 至多有 个结点，k

和结点n的关系为 。

题6.5

? 填空：一棵有100个叶子结点的完全二叉树，最多有 结点。 题6.6

? 具有n个结点的满二叉树，其叶子结点有 个。

题6.7

? 已知某字符串S共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3

次、4次和9次，对该字符串用{0, 1}进行前缀编码，问该字符串的编码至少有多少

位。

题6.8

? 填空：有n个结点的二叉树，已知叶子结点个数为n0，写出求度为1的结点的个数

n1的计算公式 ；若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式 。 题6.9

? 请编写一个函数（int LeafCount（Binary_tree BT） ），求此二叉树的叶子结点个数。有关的数据结构已描述如下： typedef struct { //二叉树结点 int data;

Binary_node *lchild; Binary_node *rchild; }Binary_node，*Binary_tree; 题6.10

? 已知某系统在通信联络中只可能出现八种字符（a，b，c，d，e，f，g，h），其概率

分别为5%, 29%, 7%, 8%, 14%, 23%, 3%, 11%，试设计对应Huffman树，根据此

Huffman树写出每个字母的赫夫曼编码。

题7.1

? 给出该图的邻接矩阵、邻接表、逆邻接表。

题7.2

设无向图的顶点个数为n，则该无向图最多有 条边。

A.n-1 B.n(n-1)/2 C.n(n+1)/2 D. n2 题7.3

? G是一个连通图，共有28条边，则该图至少有 个顶点，如果G是非连通的，

则该图至少有 个顶点。 ? A.6 B.7 C.8 D.9 题7.4

Kruskal算法的时间复杂度是 ，它对 图较为合适。

题7.5

? 用Prim算法（从顶点1出发）和Kruskal算法分别构造图G的最小生成树。 题7.6

对于如图所示的事件结点网络，求出各活动可能的最早开始时间和最晚完成时间，并问哪些活动是关键活动。

a1=4 12 a5=6 a2=3 a3=2 3 a4=4 4

题9.1

? 对长度为12的递增有序表（a1,a2,…,a12）进行折半查找，在设定查找不成功时，关

键字xa12以及ai不成功的平均查找长度是多少。

题9.2

? 若在线性表中采用折半查找法，该线性表应该（ ）。 ? A.元素按值有序 B.采用顺序存储结构 ? C.元素按值有序，且采用顺序存储结构

? D.元素按值有序，且采用链式存储结构

题9.3

已知序列17，31，13，11，20，35，25，8，4，24，40，27，请画出该序列的二叉排序树，并分别给出下列操作后的二叉树：1)插入数据9，2)删除结点17。

题9.4

含有12个结点的平衡二叉树的最大深度是 （设根结点深度为1）。 题9.5

? 在非空m阶B-树上，除根结点以外的所有其他非终端结点 。

? A.至少含有?m/2?棵子树 B.至多含有?m/2?棵子树 ? C.至少含有?m/2?棵子树 D.至多含有?m/2?棵子树

题9.6

使用哈希函数H(x)=x把一个整数值转换成散列表下标，现要把数据1、13、12、34、38、33、27、22插入到散列表，画出使用线性探测再散列构造的散列表。

题9.7

已知序列45，15，20，35，25，60，18，50，请画出依次插入该序列的的AVL树。 题10.1

? 在下列方法中，所需辅助存储量最多的是 ，所需辅助存储量最少的

是 ，平均速度最快的是 。 ? A.快速排序 B.归并排序 C.堆排序 题10.2

? 在文件“局部有序” 的情况下，最佳内部排序是 。

? A.直接插入排序 B.快速排序 C.简单选择排序

题10.3

快速排序在最坏情况下时间复杂度是O(n2)，比 的性能差。 A.堆排序 B.起泡排序 C.选择排序

题10.4

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

法是 。

? A.快速排序 B.堆排序 C.归并排序 D.直接插入排序

题10.5

判别序列（12，70，33，65，24，56，48，92，86，33）是否为小顶堆，如果不是，则把它调整为小顶堆。

不成功的平均查找长度是多少。

题9.2

? 若在线性表中采用折半查找法，该线性表应该（ ）。 ? A.元素按值有序 B.采用顺序存储结构 ? C.元素按值有序，且采用顺序存储结构

? D.元素按值有序，且采用链式存储结构

题9.3

已知序列17，31，13，11，20，35，25，8，4，24，40，27，请画出该序列的二叉排序树，并分别给出下列操作后的二叉树：1)插入数据9，2)删除结点17。

题9.4

含有12个结点的平衡二叉树的最大深度是 （设根结点深度为1）。 题9.5

? 在非空m阶B-树上，除根结点以外的所有其他非终端结点 。

? A.至少含有?m/2?棵子树 B.至多含有?m/2?棵子树 ? C.至少含有?m/2?棵子树 D.至多含有?m/2?棵子树

题9.6

使用哈希函数H(x)=x把一个整数值转换成散列表下标，现要把数据1、13、12、34、38、33、27、22插入到散列表，画出使用线性探测再散列构造的散列表。

题9.7

已知序列45，15，20，35，25，60，18，50，请画出依次插入该序列的的AVL树。 题10.1

? 在下列方法中，所需辅助存储量最多的是 ，所需辅助存储量最少的

是 ，平均速度最快的是 。 ? A.快速排序 B.归并排序 C.堆排序 题10.2

? 在文件“局部有序” 的情况下，最佳内部排序是 。

? A.直接插入排序 B.快速排序 C.简单选择排序

题10.3

快速排序在最坏情况下时间复杂度是O(n2)，比 的性能差。 A.堆排序 B.起泡排序 C.选择排序

题10.4

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

法是 。

? A.快速排序 B.堆排序 C.归并排序 D.直接插入排序

题10.5

判别序列（12，70，33，65，24，56，48，92，86，33）是否为小顶堆，如果不是，则把它调整为小顶堆。

本文来源：https://www.bwwdw.com/article/ku0w.html