搜索
更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........2003年下半年全国自考数据结构真题一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.计算机识别、存储和加工处理的对象被统称为（）A.数据B.数据元素C.数据结构D.数据类型答案：2.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（）A.AB.BC.CD.D答案：3.队和栈的主要区别是（）A.逻辑结构不同B.存储结构不同C.所包含的运算个数不同D.限定插入和删除的位置不同答案：4.链栈与顺序栈相比，比较明显的优点是（）A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况答案：5.采用两类不同存储结构的字符串可分别简称为（）A.主串和子串B.顺序串和链串C.目标串和模式串D.变量串和常量串答案：6.在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是（）A.0B.2C.3D.5答案：7.已知广义表的表头为a，表尾为（b，c），则此广义表为（）A.（a，（b，c））B.（a，b，c）C.（（a），b，c）D.（（a，b，c））答案：8.二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为（）A.470B.471C.472D.473答案：9.二叉树中第5层上的结点个数最多为（）A.8B.15C.16D.32答案：10.下列编码中属前缀码的是（）A.{1，01，000，001}B.{1，01，011，010}C.{0，10，110，11}D.{0，1，00，11}答案：11.如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是（）A.有向完全图B.连通图C.强连通图D.有向无环图答案：12.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为（）A.O（1）B.O（logn）C.O（n）D.O（nlogn）答案：13.对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为（）A.AB.BC.CD.D答案：14.对于哈希函数H（key）=key%13，被称为同义词的关键字是（）A.35和41B.23和39C.15和44D.25和51答案：15.稠密索引是在索引表中（）A.为每个记录建立一个索引项B.为每个页块建立一个索引项C.为每组记录建立一个索引项D.为每个字段建立一个索引项答案：二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。1.当问题的规模n趋向无穷大时，算法执行时间T（n）的数量级被称为算法的___。答案：2.在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作___。答案：3.已知链栈的结点结构如上图所示，栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为___和___。答案：4.空串的长度是___；空格串的长度是___。答案：5.假设一个6阶的下三角矩阵B按列优先顺序压缩存储的一维数组A中，其中A［0］存储矩阵的第一个元素b11，则A［14］存储的元素是___。答案：6.在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是___。答案：7.如下图所示的有向无环图可以排出___种不同的拓扑序列。答案：8.利用筛选法将关键字序列（37，66，48，29，31，75）建成的大根堆为（___）。答案：9.对长度为20的有序表进行二分查找的判定树的高度为___。答案：10.在多重表文件中，次关键字索引的组织方式是将___的记录链接成一个链表。答案：三、解答题（本大题共4小题，每小题5分，共20分）1.对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针p，能否将p所指结点的数据元素与其确实存在的直接前驱交换？请对每一种链表做出判断，若可以，写出程序段；否则说明理由。单链表和单循环链表的结点结构如下图a双向链表的结点结构如下图b（1）单链表（2）单循环链表（3）双向链表答案：2.假设通信电文使用的字符集为{a，b，c，d，e，f，g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。（1）请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；（2）若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。答案：3.当采用邻接表作为图的存储结构时，也可将邻接表中的顶点表由顺序结构改为链表结构。（1）请分别画出这种邻接表的顶点链表结点和边表结点，并说明结点中各个域的作用；（2）对如图所示的有向图画出这种邻接表。答案：4.已知4阶B树如图所示。（1）分别画出将关键字23和89相继插入之后的B树；（2）画出从插入之前的B树中删除关键字51之后的B树。答案：四、算法阅读题（本大题共4小题，每小题5分，共20分）1.阅读下列算法并回答问题：（1）设数组L［1..8］的初值为（4，-3，7，-1，-2，2，5，-8），写出执行函数调用f33(L,8)之后的L［1..8］中的元素值；（2）简述函数f33的功能。voidf33(intR［］,intn){intx=R［1］;intlow=1,high=n;while(lowhigh){while(lowhigh&&R［high］=0)high--;if(lowhigh){R［low++］=R［high］;while(lowhigh&&R［low］0)low++;R［high--］=R［low］;}}R［low］=x;}答案：(1)(-8,-3,-2,-1,4,2,5,7)(3分)(2)将数组R中所有负数均调整到前端，同时将所有非负数调整到后端(2分)2.阅读下列函数algo，并回答问题：（1）假设队列q中的元素为（2，4，5，7，8），其中“2”为队头元素。写出执行函数调用algo（&q）后的队列q；（2）简述算法algo的功能。voidalgo（Queue*Q）{StackS;InitStack(&S);while(!QueueEmpty(Q))Push(&S,DeQueue(Q));while(!StackEmpty(&S))EnQueue(Q,Pop(&S));}答案：3.已知邻接表的顶点表结点结构为下图(a)所示边表结点EdgeNode的结构为下图(b)所示下列算法计算有向图G中顶点vi的入度。请在空缺处填入合适的内容，使其成为一个完整的算法。intFindDegree(ALGraph*G,inti)//ALGraph为图的邻接表类型{intdegree,j;EdgeNode*p;degree=(___);for(j=0;jG-n;j++){p=G-adjlist［j］.firstedge;while((___)){if((___)){degree++;break;}p=p-next;}}returndegree;}答案：4.已知单链表的结点结构为下图下列算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。请在空缺处填入合适的内容，使其成为完整的算法。voidSelectSort(LinkedListL){LinkedListp,q,min;DataTypercd;p=(1);while(p!=NULL){min=p;q=p-next;while(q!=NULL){if((2))min=q;q=q-next;}if((3)){rcd=p-data;p-data=min-data;min-data=rcd;}(4);}}更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........答案：五、算法设计题（本题10分）1.答案：