绵阳数据结构.doc

《绵阳数据结构.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、单项选择题（本大题共20小题，每小题1分，共20分）请将正确选项前的字母填在题后的括号内。1.在顺序存储的线性表(a1,a2,...,an)中,删除任意一个结点时所需移动结点的平均次数为（）。A、nB、n/2C、(n-1)/2D、(n+1)/22.下列算法suanfa2的时间复杂度为____。intsuanfa2(intn){intt=1；while(t<=n)t=t*2；returnt；}A.O(log2n)B.O(n)C.O(n2)D.O(2n)3.____又称为FIFO表。A.队列B.栈C.散列表D.哈希表4.若6行8列的数组

2、以列序为主序顺序存储,基地址为1000,每个元素占2个存储单元,则第5行第3列的元素(假定无第0行第0列)的地址是____。A.1086B.1068C.1032D.答案A,B,C都不对5.广义表(a,((b,()),c),(d,(e)))的深度是____。A.2B.3C.4D.56.若待排序列已基本有序，要使它们完全有序，从关键码比较次数和移动次数考虑，应当使用的排序方法是（）。A、归并排序B、快速排序C、直接选择排序D、直接插入排序7.与中缀表达式a+b*c-d等价的前缀表达式是____。A.+a-*bcdB.*+-abcdC.-+a

3、*bcdD.abcd+*-8.折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次与表中元素____进行比较,。A.65,15,37B.68,30,37C.65,15,30D.65,15,30,379.对长度为10的表作选择(简单选择)排序,共需比较____次关键字。A.45B.55C.90D.11010.对n个元素的表作快速排序,在最坏情况下,算法的时间复杂度为____。A.O(log2n)B.O(nlog2n)C.O(n2)D.O(2n)11.一组记录的关键字经一趟二路归并排序后得到含有

4、5个长度为2的有序表如下：[25，48]，[16，35]，[79，82]，[23，40]，[36，72]，在此基础上按二路归并排序方法再对该序列进行一趟归并后的结果为（）。A、16，25，35，48，79，82，23，36，40，72B、16，25，35，48，23，40，79，82，36，72C、16，25，48，35，79，82，23，36，40，72D、16，25，35，48，79，23，36，40，72，8212.将线性表的数据元素以____结构存放,查找一个数据元素所需的时间不依赖于表的长度。A.循环双链表B单链表C.哈希(H

5、ash)表C.一维数组13.设依次进入一个栈的元素序列为c,a,b,d,不可得到出栈的元素序列有____。A.a.b,c,dB.a,d,b,cC.b,a,d,cD.c,d,a,b14.___又是一棵满二叉树。A.深度为5有31个结点的二叉树B.有15个结点的完全二叉树C.哈夫曼(Huffman)树D.二叉排序树15.查找哈希(Hash)表,解决冲突的的方法有__B__。A.除留余数法B.线性探测再散列法C.直接地址法D.链地址法16.算法指的是（c）A．计算机程序B．解决问题的计算方法C．解决问题的有限运算序列D．排序算法17.由__D

6、__组成的集合是一个数据对象。A.不同类型的数据项B.不同类型的数据元素C.相同类型的数据项D.相同类型的数据元素18、在一个单链表HL中，若要向q所指结点之后插入一个由指针p指向的结点，则执行  （D）      A、HL=p;p->next=HL    B、p->next=HL;HL=pC、P->next=q->next;q->next=p D、p->next=q->next;q=p>next19、由权值分别为3，8，10，2，6的叶子结点生成一棵哈夫曼树，该树中双分支结点数为 A、2 B、3 C、4   D、520．设sub(s,

7、i,j)的功能是返回串s从第i个字符开始长度为j的子串，scopy(s,t)的功能是复制串t到s，若字符串s=`SCIENCESTUDY’，则调用scopy(p,sub(s,1,7))后得到(A)A、p=`SCIENCE’B、p=`STUDY’C、s=`SCIENCE’D、s=`STUDY17.下图是一个AOV网，（B）是它的拓扑序列。ABCDEA.ABCDEB.ACDBEC.ADBCED.CADBE18.对一个算法的评价，不包括如下（D）方面的内容。A.可读性B.正确性C.时间复杂度D.并行性19.递归算法必须使用（A）。A.线性表B

8、.图C.栈D.队列20.当稀疏矩阵采用十字链表的链式存储时，它的包括元素的行号、列号、元素本身的信息和（D）的指针域。A.指向同一行中下一个有效节点的指针B.指向同一列中下一个有效节点的指针C.分别指向所在