资源描述：
《数据结构复习题及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、复习题（一）一．填空题（每空1分，共15分）1.一个算法的效率可分为___________________效率和___________________效率。2.__________________是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。3.设S=“A;/document/Mary.doc”，则strlen(S)=_______________，“/”的字符定位的位置为_______________。4.设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[
2、32,58]的存储地址为_______________。5.一棵深度为6的满二叉树有_______________个分支结点和_______________个叶子。6.用5个权值{3,2,4,5,1}构造的哈夫曼（Huffman）树的带权路径长度是。7.设有一稀疏图G，则G采用存储较省空间。8.快速排序算法是对算法的一种改进。9.在数据的存放无规律而言的线性表中进行检索的最佳方法是。10.大多数排序算法都有两个基本的操作：和。11.设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列，则：快速排序一趟
3、扫描的结果是。二．选择题（每题2分，共30分）（）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（）2.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素（A）8（B）63.5（C）63（D）7（）3.链接存储的存储结构所占存储空间：（A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针（B）只有一部分，存放结点值（C）只有一部分，存储表示结点间关系的指针（D）分两部分，一部分存放结点值，另一部分存放结点所
4、占单元数（）4.设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为P034P0àa13àa24àa30（Ａ）循环链表（Ｂ）单链表（Ｃ）双向循环链表（Ｄ）双向链表（）5．双向循环链表的每个结点中包括两个指针next和previous，分别指向该结点的后继和前驱结点。现要删除指针p所指向的结点，下面的操作序列中哪一个是正确的？（A）p-next-〉previous=p->previous;p->previous-〉next=p->next；（B）p->next-〉previous=p->next;p->previo
5、us-〉next=p->previous；（C）p->previous-〉next=p->previous;p->next-〉previous=p->next；（D）p->priou-〉next-〉next=p-next;p->next-〉previous=p->previous；（）6.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为：（Ａ）i（Ｂ）n=i（Ｃ）n-i+1（Ｄ）不确定）7.数组Q[n]用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元
6、素的个数小于n，计算队列中元素的公式为：（Ａ）r－f（Ｂ）（n＋f－r）%n（Ｃ）n＋r－f（Ｄ）（n＋r－f）%n（）8.设串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))的结果串是：（Ａ）BCDEF（Ｂ）BCDEFG（Ｃ）BCPQRST（Ｄ）BCDEFEF（）9.设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（
7、如右图所示）按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j（i≤j），在一维数组B中下标k的值是：（Ａ）i(i-1)/2+j-1（Ｂ）i(i-1)/2+j（Ｃ）i(i+1)/2+j-1（Ｄ）i(i+1)/2+j（）10.具有n(n>0)个结点的完全二叉树的深度为。（Ａ）élog2(n)ù（Ｂ）ëlog2(n)û（Ｃ）ëlog2(n)û+1（Ｄ）élog2(n)+1ù（）11.深度优先遍历类似于二叉树的（Ａ）先序遍历（B）中序遍历（C）后序遍历（D）层次遍历（）12.已知图的邻接矩阵如右图，根据算法，则从顶点
8、0出发，按深度优先遍历的结点序列是：（A）0243156（B）0135642（C）0423165（D）0134256（）13.设哈希表长度为11，哈希函数为H（key）=keym
