数据结构作业(,,)

《数据结构作业(,,)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章串一．选择题1．若串S='software',其子串的数目是（）A．8B．37C．36D．92．设有两个串p和q,求q在p中首次出现的位置的运算称作（　）A．连接　　B．模式匹配C．求串长　　D．求子串3．设字符串S1=“ABCDEFG”，S2=“PQRST”，则运算：S=CONCAT（SUBSTR（S1，2，LEN（S2））；SUBSTR（S1，LEN（S2），2））；后的串值为（　）矚慫润厲钐瘗睞枥庑赖。A．ABCDEFB．BCDEFGC．BCDPQRSTD． BCDEFEF4．下面的

2、说法中，只有（）是正确的A．串是一种特殊的线性表B．串的长度必须大于零C．串中元素只能是字母D．空串就是空白串5．两个字符串相等的条件是（）A．两串的长度相等B．两串包含的字符相同C．两串的长度相等，并且两串包含的字符相同D．两串的长度相等，并且对应位置上的字符相同二．填空题1．串“ababcbaababd”的next函数值为，nextval函数值为。2．子串的长度为。第五章数组和广义表一．选择题1．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首

3、地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为()聞創沟燴鐺險爱氇谴净。A.BA+141B.BA+180C.BA+222D.BA+225残骛楼諍锩瀨濟溆塹籟。2．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）酽锕极額閉镇桧猪訣锥。A.808B.818C.1010D.1020彈贸摄尔霁毙攬砖卤庑。3．对稀疏矩阵进行压缩存储目的是（）A．便于进行矩阵运算B．便于输入和输出C．节省

4、存储空间D．降低运算的时间复杂度4．假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（　　）謀荞抟箧飆鐸怼类蒋薔。A.B.C.D.二．解答题已知一个6行5列的稀疏矩阵中非零元的值分别为：-90，41，-76，28，-54，65，-8，它们在矩阵中的列号依次为：1，4，5，1，2，4，5。当以带行表的三元组表作存储结构时，其行表中的值依次为0，0，2，2，3，5（行列下标均从1开始），写出该稀疏矩阵。厦礴恳蹒骈時盡继價骚。第六章树和二叉树一．

5、选择题1．如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）A.栈B.队列C.树D.图2．设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A．5B．6C．7D．83．已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）A.0B.1C.48D.494．树的先根序列等同于与该树对应的二叉树的（）A．先序序列B．中序序列C．后序序列D．层序序列5.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的

6、个数为（）A．n-1B．nC．n+lD．2n6.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）茕桢广鳓鯡选块网羈泪。A．m-nB．m-n-1C．n+1D．条件不足，无法确定鹅娅尽損鹌惨歷茏鴛賴。7.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T中的叶子数为（）A．5B．6C．7D．88．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是

7、（）籟丛妈羥为贍偾蛏练淨。A．M1B．M1+M2C．M3D．M2+M39．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A．250B．500C．254D．505E．以上答案都不对預頌圣鉉儐歲龈讶骅籴。10．有n个叶子的哈夫曼树的结点总数为（）A．不确定B．2nC．2n+1D．2n-111．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有()结点A．2hB．2h-1C．2h+1D．h+112．将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（）A

8、．4B．5C．6D．713．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（）A．n-1B．ën/mû-1C．é(n-1)/(m-1)ùD．én/(m-1)ù-1E．é(n+1)/(m+1)ù-1渗釤呛俨匀谔鱉调硯錦。14．若下面几个符号串编码集合中，不是前缀编码的是（）。A．{0,10,110,1111}B．{11,10,001,101,0001}铙誅卧泻噦圣骋贶頂廡。C．{00,010,0110,1000}D．{b,c,aa,ac,aba,abb,abc}擁締凤袜备訊顎轮烂蔷。1