发布时间 : 星期四 文章数据结构习题1更新完毕开始阅读0c9897303968011ca30091a9
2 2
1
5 编写一个算法，利用栈的基本运算返回指定栈中的栈底元素。
习
一、选择题
题4
1 串是一种特殊的线性表，其特殊性体现在（ ） A 唯一可以顺序存储 B 数据元素是一个字符 C 可以链接存储 D 数据元素可以是多个字符 2 下面（ ）是C语言中“abcd321ABCD”的子串。
A abcd B 321AB C “abcAB” D “21AB” 3 设有两个串p和q，求p和q首次出现的位置的运算称作( ) A 连接 B 模式匹配 C 求子串 D 求串长 4 设有一个字符串S=“windows”，求子串的数目是（） A 25 B 26 C 27 D 28
二、简答题
1 空串与空格串有什么区别？字符串中的空格有什么意思？空串在串的处理中有什么作用？
2串是由字符组成的，长度为1的串和字符是否相同？为什么？
3简述串的静态顺序存储结构与动态顺序存储结构有什么区别，分别写出它们的结构体定义。
4字符串采用静态顺序存储结构。编写一个算法删除S中地i个字符到第j个字符。 5编写一个算法判断s2是否是s1的子串。
习
一、选择题
题5
1．二维数组A行下标i的范围从1到12，列下标j的范围从3到10，采用行序为主序存储，每个数据元素占用4个存储单元，该数组的首地址（即A[1][3]的地址）为1200，则A[6][5]的地址为（ ）。
A 1400 B 1404 C 1372 D 1368
2．二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素（ ）的起始地址相同。
A M[2][4] B M[3][4] C M[3][5] D M [4][4]
3．数组A中，每个元素A的长度为3个字节，行下标i从1到5，列下标j从1到6，从首地址开始连续存放在存储器内，存放该数组至少需要的单元数是（ ）。
8
A 90 B 70 C 50 D 30
4．设有10阶矩阵A，其对角线以上的元素aij均取值为-3，其他矩阵元素为正整数，现在将矩阵A压缩存放在一维树组F[m]中，则 m为（ ）。 A 45 B 46 C 55 D 56 5．若广义表A满足head(A)=tail(A),则A为（ ）。
A （ ） B （（）） C （（），（）） D （（），（），（）） 6．递归函数f(n)=f(n-1)+n(n>1)的递归出口是（ ）
A f(1)=0 B f(1)=1 C f(0)=1 D f(n)=n
二、简答题
1．什么叫二维数组的行序优先存储？什么叫二维数组的列序优先存储？ 2．什么样的矩阵叫特殊矩阵？特殊矩阵压缩存储的基本思想是什么？ 3．什么样的矩阵叫稀疏矩阵？稀疏矩阵压缩存储的基本思想是什么？
三、计算题
设有二维数组A（6*8），每个元素占4个字节，A[0][0]的起始地址为1000，计算 （1） 数组A共占多少个字节；
（2） 数组的最后一个元素A[5][7]的起始地址； （3） 按行优先存放时，元素A[1][4]的起始地址； （4） 按列优先存放时，元素A[4[7]的起始地址；
四、设计题
1．对于二维数组A[m][n]，其中m<=80，n<=80，先读入m和n ，然后读该数组的全部元素，对如下三种情况分别编写相应函数： （1）求数组A靠边元素之和；
（2）求从A[0][0]开始的互不相邻的各元素之和；
（3）当m=n时，分别求两条对角线上的元素之和，否则打印出m!=n的信息。
2．有数组A[4][4]，把1到16个整数分别按顺序放入A[0][0]，??，A[0][3]，A[1][0]，??，A[1][3]，A[2][0]，??，A[2][3]，A[3][0]，??，A[3][3]中，编写一个函数获得数据并求出两条对角线元素的乘积。
习
一、选择题
题6
1、下述编码中哪一个不是前缀编码（A ）
A、｛00，01，10，11｝ B、｛01，0，1，10｝ C、｛0，10，110，111｝ D、｛1，01，000，111｝ 2、一棵二叉树第五层的结点数最多为（A ）
A、16 B、15 C、8 D、32
3、利用3、8、12、6这4个值作叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为（A ）
A、55 B、29 C、58 D、38
4、在线索化二叉树中，t所指节点没有左子树的充要条件是（ ）
9
A、t->left=NULL B、t->ltag=1 C、t->ltag=1且t->left=NULL D、以上都不对
5、设高度为h的二叉数上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（B ）
A、2h B、2h -1 C、2h +1 D、h+1 6、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（ D） A、acbed B、 decab C、 deabc D 、cedba 7、按照二叉树的定义，具有三个节点的二叉树有（C）种
A、3 B、4 C、5 D、6
8、任意一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ A ） A、不发生改变 B、发生改变 C、不能确定 D、以上都不对 9、对一个满二叉树，它有m个树叶，n个结点，深度为h，则（D） A、n=h+m B 、h+m=2n C、m=h-1 D 、n=2-1
h
二、设计题
1、已知一棵树的边的集合表示为{（L,N）,（G,K）,（G,1）,（G,M）,（B,E）,（B,F）,（D,G）,（D,H）,（D,I）,（D,J）,（A,B）,（A,C）,（A,D）}。画出这棵树并回答下面问题： （1） 树的根节点是哪个，哪些是叶子结点，哪些是非终端结点。 （2） 树的深度是多少，各个结点的层数是多少。
（3） 对于G结点，它的双亲结点、祖先结点、孩子结点、子孙结点、兄弟和堂兄弟分别是哪些结点。
2、给定二叉树的先序序列和中序序列，能否重构出该二叉树？给定二叉树的先序序列和后序序列呢？若不能，给出反例。
3、一棵深度为h的满二叉树具有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有m棵非空子树。若按层次从上到下，每层从左到右的顺序从1开始对全部结点编号，试计算：
（1）第k层结点数（1＜＝k＜＝h）。
（2）整棵树结点数
（3）编号为i的结点的双亲结点的编号
（4）编号为i的结点的第j个孩子结点（若有）的编号
4、若7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶结点构造一棵哈夫曼树（请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造），度计算出带权路径长度WPL及该树的结点总数。
5、假设二叉数采用链式存储结构，编写一个算法释放该二叉树所占用的全部结点。 6、编写一个计算一棵二叉树T的高度算法。
7、二叉树采用二叉树链表的结构存储，设计一个算法求二叉树中指定结点的层数。
习
一、选择题
题7
1、 在一个具有n个顶点的无向图中，要连接全部顶点至少需要（ ）条边。 A、n B、n＋1 C、n－1 D、n/2
2、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ） A、n B、(n-1)/2 C、n-1 D、n2
10
3、具有6个顶点的无向图至少应用（ ）条边才能确保是一个连通图。 A、5 B、6 C、7 D、8
4、n个顶点的强连通图的邻接矩阵中至少有（ ）个非零元素。 A、n-1 B、n C、2n-2 D、2n
5、在一个具有n个顶点的有向完全图中，所含的边数为（ ）
A、n B、n(n-1) C、n(n-1)/2 D、n(n+1)/2
6、在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（ ）。
A、n B、ne C、e D、2e
7、在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链接的表头指针向量大小至少为（ ）
A、n B、2n C、e D、2e
8、在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为（ ）。 A、n B、ne C、e D、e
9、对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的边结点数为（ ）
A、k1 B、k2 C、k1-k2 D、k1+k2
10、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ ） A、接层遍历 B、中序遍历 C、先序遍历 D、后序遍历
11、无向图G＝（V，A），其中V＝｛a,b,c,d,e｝, A={
A、adcbe B、dabce C、abdce D、abcde
12、G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。 A、7 B、8 C、9 D、10
二、简答题
1、 对于一个有向图，不用拓扑排序，如何判定图中是否存在环？
2、 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边数是否相关？
习
一、选择题
题8
1、 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找
一个记录，其平均查找长度ASL为（ ） A、（n-1）/2 B、n/2 C、(n+1)/2 D、n
2、下面关于二分查找叙述正确的是（ ）
A、表必须有序，表可以顺序方式存储，也可以链表方式存储 B、表必须有序且表中数据必须是整型，实型或字符型 C、表必须有序，而且只能从小到大排序
D、表必须有序，且表只能以顺序方式存储
3、当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）
11