东北农业大学网络教育学院 数据结构专升本作业题
作业题（一）
一、单项选择题
1. 从逻辑上可以把数据结构分为（C ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 2. 链表不具有的特点是（ B ）
A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 3.下面程序段的时间复杂度的量级为（ D ）。 For(i=1;i<=n;i++) For(j=1;j<=I;j++) For(k=1;k<=j;k++) X=x+1;
A．O(1) B．O(n) C．O(n2) D．O(n3)
4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（B ）个指针域的值。
A．2 B3 C．4 D．6
5、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（ D ）。
A．98 B．100 C．102 D．106 6、判定一个栈s（最多元素为m0）为空的条件是（ B ）。 A．s-〉top! =0 B．s-〉top= =0 C．s-〉top! =m0 D．s-〉top= =m0
7、循环队列用数组A[m]（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（ ）。
A．（rear-front+m）%m B．rear-front+1 C．rear-front-1 D． rear-front
8、设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（ ）。
A．连接 B．求子串
1
C．模式匹配 D．判子串
9、设串S1='ABCDEFG'，S2='PQRST'，函数con（x，y）返回x和y串的连接串，subs(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 10、数组常用的两种基本操作是（ ）。
A．建立与查找 B．删除与查找 C．插入与索引 D．查找与修改 二、填空题
1. 所谓稀疏矩阵指的是________且分布没有规律。 2. 队列是________的线性表，其运算遵循________的原则。 3. 空格串是________________________________。
4.简单选择排序和起泡排序中比较次数与序列初态无关的算法有________。
5、设图G有n个顶点和e条边，则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度为 ，而对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为 ，图的深度或广度优先搜索遍历时的空间复杂度均为 。
6、一个图的 表示法是唯一的，而 表示法是不唯一的。 三、算法
设二叉树采用二叉链表结构，试设计一个算法统计给定二叉树中的一度结点数目。 四、应用题
1、对关键字无序序列(36，25，48，12，65，43，20，58)进行直接选择排序，请写出每一趟排序的结果。（10分）
2、对无向带权图，用克鲁斯卡尔算法构造最小生成树。（10分）
3、已知记录关键字集合为（53,17,19,61,98,75,79,63,46,49）要求散列到地址区间（100,101,102,103,104,105,106,107,108,109）内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的散列函数；形成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。（设
2
1 G C 20 9 B 5 8 E 2 6 F A 3 D 4 等概率情况）
4、设被查找文件有4095个记录，对每个记录查找记录概率相等，若采用顺序查找，成功查找平均比较次数为多少
作业题（二）
、单项选择题
1. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列（ ）
A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 2. 栈和队都是（ ）
A．顺序存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构 3、顺序查找法适合于存储结构为（ ）的线形表。
A．散列存储 C．压缩存储
B．顺序存储或链接存储 D．索引存储
4、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。
A．（100，80， 90， 60， 120，110，130） B．（100，120，110，130，80， 60， 90） C．（100，60， 80， 90， 120，110，130） D． (100，80， 60， 90， 120，130，110) 5、折半查找的平均比较次数为（ ）。
A．n
B．n/2 D．log2(n+1)
C．log2n
6、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）
A．必定快
B．不一定 3
C．在大部分情况下要快 D．取决于表递增还是递减
7、已知一有向图的邻接表存储结构如下图如示。根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是（ ）。
A．v1，v2，v3，v5，v4 C．v1，v3，v4，v5，v2
B．v1，v2，v3，v4，v5 D．v1，v4，v3，v5，v2
8、为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用（ ）。
A．顺序存储 C．索引存储
B．链式存储 D．散列存储
9、在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（ ）。
A．s
B．s-1 D．n
C．s+1
10、如图所示，给出由7个顶点组成的无向图。从顶点A出发，对它进行深度优先搜索得到的顶点序列是（ ）。
A．A E C D B F G C．A C E D B G F
B．A G B F D E C D．A B D G F E C
二、填空题
1. 设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有________个结点。
2. 有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是________，带权路径长度WPL为________。
3.设一棵完全二叉树叶子结点数为k,最后一层结点数>2，则该二叉树的高度为________________。 4. 采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分 个结点最佳。
5、设G为具有N个顶点的无向连通图，则G中至少有 条边。
6、哈夫曼树（Huffman Tree）又称 。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL 。
7、树的先序遍历过程如下：若树为空，则进行空操作；若树非空，则访问树的 ；依次先序遍历树
4
的 。 三、应用题
1、给定权值集合{1, 4, 2, 6, 9,}, 构造相应的哈夫曼树, 并计算它的带权路径长度。
2、对关键字序列{10，6，3，2，5，4}，构造一棵平衡二叉（排序）树并画图（要求画出建树过程）。
3、设有一个有序文件，其中各记录的关键字为（1，2，3，4，5，6，7，8，9，10，11，12，13，14，15），当用折半查找算法查找关键字为3，8，19时，其比较次数分别为多少 4、对有五个结点{ A,B, C, D, E}的图的邻接矩阵， ?010030?10???0????????60020??????10?0???????500?? （1）．画出逻辑图 ；
（2）．画出图的十字链表存储；
（3）．基于邻接矩阵写出图的深度、广度优先遍历序列； （4）．计算图的关键路径。
作业题（三）
一、单项选择题 1．串的长度是指（ ）
A．串中所含不同字母的个数 B．串中所含非空格字符的个数 C．串中所含不同字符的个数 D．串中所含字符的个数
2．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 3．算法分析的两个主要方面是（ ）。
A．空间复杂性和时间复杂性 B．正确性和简明性
5
数据结构专升本模拟试题及参考答案
