兰州大学数据结构平时作业3-00001试卷总分100 得分100一、单选题 (共 10 道试题,共 50 分)1.广义表（ab）,ab）的表头是( ) 。A.abB.abC.（ab）D.(ab)答案C2.对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为（ ）。A.2B.3C.4D.5答案C3.在下面的排序方法中，辅助空间为O（n）的是( )A.希尔排序B.堆排序C.选择排序D.归并排序答案D4.已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，查找成功的比较次数为（）A.1B.2C.3D.4答案B5.用不带头结点的单链表存储队列,其队头指针指向队头结点,队尾指针指向队尾结点,则在进行出队操作时()A.仅修改头队头指针B.仅修改队尾指针C.队头队尾指针都修改D.队头队尾都可能被修改答案D6.如下陈述中正确的是（ ）A.串是一种特殊的线性表B.串的长度必须大于零C.串中元素只能是字母D.空串就是空白串答案A7.计算机算法必须具备输入、输出和 等5个特性。A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性答案B8.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。A.快速排序B.堆排序C.归并排序D.直接插入排序答案C9.数据结构是一门研究非数值的程序设计问题中计算机的 以及它们之间的 关系 和运算等的学科A.操作对象B.计算方法C.逻辑存储D.物理存储答案A10.若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为（ ）。A.nB.n+1C.(n-1)2D.(n+1)2答案D二、判断题 (共 10 道试题,共 50 分)11.一个深度为5的二叉树至多有31个节点答案正确12.归并排序是一种稳定的排序方法。（ ）答案正确13.完全二叉树中的叶子结点只可能在最后两层中出现。（ ）答案正确14.对于哈希函数，冲突只能尽可能得少，不可能完全避免。（ ）答案正确15.队列是先进先出的线性表答案正确16.邻接表法只能用于有向图存储答案错误17.如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（ ）答案正确18.数据结构是带有结构的数据元素的集合答案正确19.希尔排序是一种稳定的排序方法。（ ）答案正确20.哈夫曼树是带权路径长度最短的树。（ ）答案正确