16春天大数据结构在线作业一

1、数据结构在线作业一 一、单选题（共 40 道试题，共 100 分。）1. 设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ ）。. O(1). O(log2n). O(n4). O(n2 )正确答案：2. 对一个满二叉树，m个树叶，n个结点，深度为h，则（）。. n=h+m. h+m=2n. m=h-1. n=2的h次方-1正确答案：3. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。. O(n). O(nlog2n). O(1). O(n2 )正确答案：4. 已知某二叉树的后序遍历序列是，中序遍历序列是，它的前序遍历序列是（）。. . . . 正确答

2、案：5. 以下数据结构中哪一个是非线性结构？( ). 队列. 栈. 线性表. 二叉树正确答案：6. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行（）。(不带空的头结点). HSnxt=s;. snxt= HSnxt;HSnxt=s;. snxt= HS;HS=s;. snxt= HS;HS= HSnxt;正确答案：7. 设某强连通图中有n个顶点，则该强连通图中至少有（ ）条边。. n(n-1). n+1. n. n(n+1)正确答案：8. 一个栈的入栈序列，则栈的不可能的输出序列是（）。. . . . 正确答案：9. 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，

3、p3，pn，若p1=n，则pi为（）。. i. n=i. n-i+1. 不确定正确答案：10. 在二叉排序树中插入一个结点的时间复杂度为（ ）。. O(1). O(n). O(log2n). O(n2 )正确答案：11. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为( ). O（1）. O（n）. O（1og2n）. O（n2）正确答案：12. 设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )。. 10，15，14，18，20，36，40，21. 10，15，14，18，20，40，36，21. 1

4、0，15，14，20，18，40，36，2l. 15，10，14，18，20，36，40，21正确答案：13. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是（） 。. 4，3，2，1. 1，2，3，4. 1，4，3，2. 3，2，4，1正确答案：14. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。. 2m-1. 2m. 2m+1. 4m正确答案：15. 二维数组中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址S开始连续存放在存储器内，该数组按列存放时，元素47的起始地址为（）。. S+141. S

5、+180. S+222. S+225正确答案：16. 在数据结构中，从逻辑上可以把数据结构分成（）。. 动态结构和静态结构. 紧凑结构和非紧凑结构. 线性结构和非线性结构. 内部结构和外部结构正确答案：17. 设串s1='FG'，s2='PQRST'，函数on(x,y)返回x和y串的连接串，sus(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，ln(s)返回串s的长度，则on(sus(s1,2,ln(s2),sus(s1,ln(s2),2)的结果串是（）。. F. FG. PQRST. FF正确答案：18. 设无向图的顶点个数为n，则该图最多有（

6、 ）条边。. n-1. n(n-1)/2. n(n+1)/2. 0正确答案：19. 设有两个串p和q，求q在p中首次出现的位置的运算称作（）。. 连接. 模式匹配. 求子串. 求串长正确答案：20. 在一棵具有5层的满二叉树中结点数为（ ）. 33. 32. 31. 31正确答案：21. 设一棵二叉树的深度为k，则该二叉树中最多有（ ）个结点。. 2k-1. 2k. 2k-1. 2k -1正确答案：22. 在以下的叙述中，正确的是（）。. 线性表的顺序存储结构优于链表存储结构. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况.

7、线性表的链表存储结构优于顺序存储结构正确答案：23. 设串的长度为n，则它的子串个数为（）。. n. n(n+1). n(n+1)/2. n(n+1)/2+1正确答案：24. 哈希表中的冲突可以通过改变哈希函数完全避免。. 正确. 错误正确答案：25. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。. 不发生改变. 发生改变. 不能确定. 以上都不对正确答案：26. 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。. 3. 4. 5. 8正确答案：27. 从一个栈顶指针为HS的

8、链栈中删除一个结点时，用x保存被删结点的值，则执行（）。(不带空的头结点). x=HS;HS= HSnxt;. x=HSt;. HS=HSnxt;x=HSt;. x=HSt;HS= HSnxt;正确答案：28. 若有18个元素的有序表存放在一维数组19中，第一个元素放1中，现进行二分查找，则查找3的比较序列的下标依次为( ). 1，2，3. 9，5，2，3. 9，5，3. 9，4，2，3正确答案：29. 设指针变量p指向单链表中结点，若删除单链表中结点，则需要修改指针的操作序列为（ ）。. q=p->nxt；p->t=q->t；p->nxt=q->nxt；fr(q

9、)；. q=p->nxt；q->t=p->t；p->nxt=q->nxt；fr(q)；. q=p->nxt；p->nxt=q->nxt；fr(q)；. q=p->nxt；p->t=q->t；fr(q)正确答案：30. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点。. n. n/2. (n-1)/2. (n+1)/2正确答案：31. 常对数组进行的两种基本操作是（）。. 建立与删除. 索引和修改. 对数据元素的存取和修改. 查找与索引正确答案：32. 对于线性表（7，34，55，25，

10、64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个. 1. 2. 3. 4正确答案：33. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。. 15. 16. 17. 47正确答案：34. 设无向图G中有n个顶点，则该无向图的最小生成树上有（ ）条边。. n. n-1. 2n. 2n-1正确答案：35. 某二叉树的前序遍历结点访问顺序是gfh，中序遍历的结点访问顺序是ghf，则其后序遍历的结点访问顺序是（）。. gfh. gfh. ghf. ghf正确答案：36. 判定一个循环队列QU（最多元素为m0）为空的条件是（）。. rr - front= =m0. rr-front-1= =m0. front= = rr. front= = rr+1正确答案：37. 设顺序循环队列Q0：M-1的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。. R-F. F-R. (R-F+M)M. (F-R+M)M正确答案：38. 数据结构S(t Strut)可以被形式地定义为S=（，R），其中是（）有限集合，R是上的关系有限集合。. 算法. 数据元素. 数据操作