2021年数据结构题库.doc

线性构造题
1. 栈和队列共同特点是( A )。
(A) 只容许在端点处插入和删除元素
(B) 都是先进后出
(C) 都是先进先出
(D) 没有共同点
2. 如下数据构造中哪一种是非线性构造？( D )
(A) 队列 　 (B) 栈 (C) 线性表 　　(D) 二叉树
3. 设有一种二维数组A[m][n]，假设A[0][0]存储位置在644(10)，A[2][2]存储位置在676(10)，每个元素占一种空间，问A[3][3](10)存储在( C )位置。脚注(10)表达用10进制表达。
(A) 688 (B) 678 (C) 692 (D) 696
4．设某数据构造二元组形式表达为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是（ B ）。
(A) 线性构造 (B) 树型构造 (C) 物理构造 (D) 图型构造
5．下面程序时间复杂为（ B ）
for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*js=s+t；}
(A) O(n) (B) O(n2) (C) O(n3) (D) O(n4)
6.下列程序段时间复杂度为（ A ）。
i=0，s=0； while (s按行序为主序存储，每个元素占4个字节空间，若数组a首元素a[1][1]地址为，计算a[23][21]内存地址为（ B ）。
(A)5600 (B)5612 (C)2912 (D)3600
9．设输入序列为1、2、3、4、5、6，则通过栈作用后可以得到输出序列为（ B ）。
(A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1
(C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3
10．设有一种10阶下三角矩阵A（涉及对角线），按照从上到下、从左到右顺序存储到持续55个存储单元中，每个数组元素占1个字节存储空间，则A[5][4]地址与A[0][0]地址之差为（ B ）。
(A) 10 (B) 19 (C) 28 (D) 55
11．广义表A=（a,b（c,d）,(e,(f,g))），则head(tail(head(tail(tail(A)))))值为（ D ）
(A)（g） (B)(d) (C)(c) (D)(d)
12．数据最小单位是（ A ）。
(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量
13．函数substr(“DATASTRUCTURE”，5，9)返回值为（ A ）。
(A) “STRUCTURE” (B) “DATA”
(C) “ASTRUCTUR” (D) “DATASTRUCTURE”
14．在线性表中，一种向量第一种元素存储地址是100，每个元素长度为2，则第5个元素地址是（ A ）。
（A）110 （B）108 （C）100 （D）120
15．栈中元素进出原则是（ B ）。
（Ａ）先进先出 （B）后进先出 （Ｃ）栈空则进 （Ｄ）栈满则出
16．设指针q指向单链表中结点A，指针p指向单链表中结点A后继结点B，指针s指向被插入结点X，则在结点A和结点B插入结点X操作序列为（ B ）。
(A) s->next=p->next；p->next=-s； (B) q->next=s； s->next=p；
(C) p->next=s->next；s->next=p； (D) p->next=s；s->next=q；
非线性构造
1.具备n(n>0)个结点完全二叉树深度为 C 。
(Ａ) élog2(n)ù (Ｂ) ë log2(n)û (Ｃ) ë log2(n) û+1 (Ｄ) élog2(n)+1ù
2.树最适合用来表达( C )。
(A) 有序数据元素 (B) 无序数据元素
(C) 元素之间具备分支层次关系数据 (D) 元素之间无联系数据
3.二叉树第k层结点数最多为( D ).
(A) 2k-1 (B) 2K+1 (C) 2K-1 　　　(D) 2k-1
4．设一棵完全二叉树有700个结点，则共有( D )个叶子结点。
（A）200 （B）250 （C）300 （D）350
5.若有18个元素有序表存储在一维数组A[19]中，第一种元素放A[1]中，现进行二分查找，则查找A［3］比较序列下标依次为( D )
(A) 1，2，3 (B) 9，5，2，3
(C) 9，5，3 (D) 9，4，2，3
6.对n个记录文献进行迅速排序，所需要辅助存储空间大体为( C )
(A) O（1） (B) O（n）　　 (C) O（1og2n） (D) O（n2）
7．设一组初始核心字记录核心字为(20，15，14，18，21，36，40，10)，则以20为基准记录一趟迅速排序结束后成果为( A )。
(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
8．设无向图G中有n个顶点e条边，则其相应邻接表中表头结点和表结点个数分别为（ D ）。
(A) n，e (B) e，n (C) 2n，e (D) n，2e
9．设有5000个待排序记录核心字，如果需要用最快办法选出其中最小10个记录核心字，则用下列（ B ）办法可以达到此目。
(A) 迅速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序
10.下列四种排序中（ D ）空间复杂度最大。
(A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序
11．设一棵二叉树深度为k，则该二叉树中最多有（ D ）个结点。
(A) 2k-1 (B) 2k (C) 2k-1 (D) 2k-1
12．设一组初始记录核心字序列为(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
13．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ B ）次。
(A) 25 (B) 10 (C) 7 (D) 1
14．设某棵二叉树高度为10，则该二叉树上叶子结点最多有（ C ）。
(A) 20 (B) 256 (C) 512 (D) 1024
15．在一种具备n个顶点无向连通图中,要连通所有顶点至少需要（ C ）条边。
（A） n （B） n+1 （C） n-1 （D） n/2
16.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1元素有（ D ）个，
(A) 1 (B) 2 (C) 3 (D)4
17.设有6个结点无向图，该图至少应有( A )条边才干保证是一种连通图。
(A) 5 (B) 6 (C) 7 (D) 8
18. 二叉排序树中左子树上所有结点值均（ A ）根结点值。
(A) < (B) > (C) = (D) !=
19. 设一组权值集合W=(15，3，14，2，6，9，16，17)，规定依照这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树带权途径长度为（ D ）。
(A) 129 (B) 219 (C) 189 (D) 229
20.设某棵二叉树中只有度数为0和度数为2结点且度数为0结点数为n，则这棵二叉中共有（ C ）个结点。
(A) 2n (B) n+l (C) 2n-1 (D) 2n+l
21.设一组初始记录核心字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序第一趟冒泡排序结束后成果是（ D ）。
(A) F，H，C，D，P，A，M，Q，R，S，Y，X
(B) P，A，C，S，Q，D，F，X，R，H，M，Y
(C) A，D，C，R，F，Q，M，S，Y，P，H，X
(D) H，C，Q，P，A，M，S，R，D，F，X，Y
22.设用邻接矩阵A表达有向图G存储构造，则有向图G中顶点i入度为（B ）。
(A) 第i行非0元素个数之和 (B) 第i列非0元素个数之和
(C) 第i行0元素个数之和 (D) 第i列0元素个数之和

填空题：
1. 设F和R分别表达顺序循环队列头指针和尾指针，该队列最存储空间为N个，则判断该循环队列为空条件为___F==A________，判断队列为满时条件为 (R+1)%N==F 。
2. 一种线性表是n≧0个数据元素a1,a2,a3,……an有限序列，表中每个数据元素，除第一种和最后一种外，有且仅有一种 直接前驱 和一种 直接后继 。
3. 无论是顺序存储构造栈还是链式存储构造栈，其入栈和出栈操作时间复杂度均为_0(1)_____。
4. 设输入序列为1、2、3，则通过栈作用后可以得到___5_____种不同输出序列。
5. 若用链表存储一棵二叉树时，每个结点除数据域外，尚有指向左孩子和右孩子两个指针。在这种存储构造中，n个结点二叉树共有____2n___个指针域，其中有___n-1__个指针域是存储了地址，有_____n+1____个指针是空指针。
6. 对于一种具备n个顶点和e条边有向图和无向图，在其相应邻接表中，所含边结点分别有_ ___个和______个。在一种具备n个顶点无向完全图中，包具有________条边，在一种具备n个顶点有向完全图中，包具有________条边。
7. 在迅速排序、堆排序、归并排序中，___归并______排序是稳定。
8. ___中序_______遍历二叉排序树中结点可以得到一种递增核心字序列（填先序、中序或后序）。
9. 设查找表中有100个元素，如果用二分法查找办法查找数据元素X，则最多需要比较____7____次就可以断定数据元素X与否在查找表中。
10. 设有向图G中有n个顶点e条有向边，所有顶点入度数之和为d，则e和d关系为___e=d______。设某无向图中顶点数和边数分别为n和e，所有顶点度数之和为d，则e=__d/2_____。
11. 设一组初始记录核心字序列为(55，63，44，38，75，80，31，56)，则运用筛选法建立初始堆为___31,38,44,56,75,80,55,63_____。
12. 已知一有向图邻接表存储构造如下：从顶点1出发，深度优先搜索（Dfs）输出序列是 1,3,4,5,2 ，广度优先搜索（BFS）遍历输出序列是 1,3,2,4,5

假定一种线性表为(12,23,74,55,63,40)，若给出哈希函数H（key）=Key % 4条件进行划分，使得同一余数元素成为一种子表，则得到四个子表分别为____________________________、__________________和__________________________。
13.
14. 设有n个结点完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点双亲结点编号为__i/2__________，右孩子结点编号为___2i+1_____。
15. 设一组初始记录核心字为(72，73，71，23，94，16，5)，则以记录核心字72为基准一趟迅速排序成果为___________________________。
16. 设有向图G中有向边集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图一种拓扑序列为__1,4,2,3___。
17. 设哈夫曼树中共有n个结点，则该哈夫曼树中有____0__个度数为1结点。
18. 设有向图G用邻接矩阵A[n][n]作为存储构造，则该邻接矩阵中第i行上所有元素之和等于顶点i_行为出度_，第i列上所有元素之和等于顶点i_行为入度_。
19. 为了能有效地应用HASH查找技术，必要解决两个问题是_构造好hash函数__和___拟定解决冲突办法__。
20. 中序遍历二叉排序树所得到序列是___有序___序列（填有序或无序）。
21. 折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28,6,12,20 比较大小。
22. 线性构造中元素之间存在 一对一 关系，树形构造中元素之间存在 关系 一对多 ，图形构造中元素之间存在 多对多 关系。
问答题
1. 设某棵二叉树中序遍历序列为DBEAC，前序遍历序列为ABDEC，规定给出该二叉树后序遍历序列并画出该二叉树。

2．已知待散列线性表为（36，15，40，63，22），散列用一维地址空间为[0..6]，假定选用散列函数是H（K）= K mod 7，若发生冲突采用线性探查法解决，试：计算出每一种元素散列地址并在下图中填写出散列表：
` 0 1 2 3 4 5 6

3． 设无向图G（如右图所示），画出该图最小生成树构造，并写出该图最小生成树边集合及计算最小生成树各边上权值之和。

4．已知序列（10，18，4，3，6，12，1，9，18*，8）请用迅速排序写出每一趟排序成果。

5．设一组初始记录核心字序列为(45，80，48，40，22，78)，则分别给出第4趟直接选取排序和第4趟直接插入排序后成果。

6．给定一组权值{2，8，5，4，3}，构造相应哈夫曼树。

7．下图所示森林：　　
(1) 求树（a）先根序列和后根序列；
（2）将此森林转换为相应二叉树；

8．设散列表地址范畴是[ 0..9 ]，散列函数为H（key）= （key 2 +2）MOD 9,并采用链表解决冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表存储构造。

四、算法填空题
1. 折半查找算法：
Int BinSrch(Record L,keyType k)
/*在有序表L中折半查找其核心字等于K元素，若找到，则函数值为该元素在表中位置*/
Low=1
High=L.length;
While(Low<=high)
{ (1) ； /*取列表元素中间元素位置*/
If (k==L.r[mid].key) return(mid)；/*找到待查元素K，将位置返回*/
Else if(knt val;
};
typedef struct node NODE;

void trans1(NODE a[],NODE b[])
{int col,k,q,n,t;
n=a[0].j;/*M列数*/
t=a[0].val;/*非0元素个数*/
b[0].i=a[0].j;
b[0].j=a[0].i;
b[0].val=a[0].val;
if (t>0)/*若存在非0元素*/
{q=1;/*b中当前行*/
for(col=1;col<= n ;col++)/*遍历M列*/
for(k=1;k<=t;k++)
if(a[k].j==col)
{b[q].i= (1) ;
b[q].j= (2) ;
b[q].val= (3) ;
q++;
}
}
}