《16春天大《数据结构》在线作业一》由会员分享，可在线阅读，更多相关《16春天大《数据结构》在线作业一（7页珍藏版）》请在金锄头文库上搜索。
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. 一个栈的入栈序列， ， ， ，
3、，则栈的不可能的输出序列是（） 。. . . . 正确答案： 9. 若已知一个栈的入栈序列是 1，2，3，n，其输出序列为 p1，p2，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
4、，36，40，10)，则以 20 为基准 记录的一趟快速排序结束后的结果为( )。 . 10，15，14，18，20，36，40，21 . 10，15，14，18，20，40，36，21 . 10，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
5、. 2m . 2m+1 . 4m 正确答案： 15. 二维数组中，每个元素的长度为 3 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到 9，从 首地址 S 开始连续存放在存储器内，该数组按列存放时，元素47的起始地址为（） 。. S+141 . S+180 . S+222 . S+225 正确答案： 16. 在数据结构中，从逻辑上可以把数据结构分成（） 。 . 动态结构和静态结构 . 紧凑结构和非紧凑结构 . 线性结构和非线性结构 . 内部结构和外部结构 正确答案： 17. 设串 s1=FG，s2=PQRST，函数 on(x,y)返回 x 和 y 串的连接串，sus(s,i,j)返
6、回串 s 的从序号 i 的字符开始的 j 个字符组成的子串，ln(s)返回串 s 的长度，则 on(sus(s1,2,ln(s2),sus(s1,ln(s2),2)的结果串是（） 。. F . FG . PQRST . FF 正确答案： 18. 设无向图的顶点个数为 n，则该图最多有（ ）条边。. n-1 . n(n-1)/2 . n(n+1)/2 . 0 正确答案： 19. 设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作（） 。 . 连接 . 模式匹配 . 求子串 . 求串长 正确答案： 20. 在一棵具有 5 层的满二叉树中结点数为（ ）. 33 . 32 . 31.
7、31 正确答案： 21. 设一棵二叉树的深度为 k，则该二叉树中最多有（ ）个结点。. 2k-1 . 2k . 2k-1 . 2k -1 正确答案： 22. 在以下的叙述中，正确的是（） 。 . 线性表的顺序存储结构优于链表存储结构 . 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况 . 线性表的链表存储结构适用于频繁插入/删除数据元素的情况 . 线性表的链表存储结构优于顺序存储结构 正确答案： 23. 设串的长度为 n，则它的子串个数为（） 。. n . n(n+1) . n(n+1)/2 . n(n+1)/2+1 正确答案： 24. 哈希表中的冲突可以通过改变哈希函数完全避免。 .
8、 正确 . 错误 正确答案： 25. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（） 。 . 不发生改变 . 发生改变 . 不能确定 . 以上都不对 正确答案： 26. 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。. 3 . 4 . 5 . 8 正确答案： 27. 从一个栈顶指针为 HS 的链栈中删除一个结点时，用 x 保存被删结点的值，则执行（） 。 (不带空的头结点) . x=HS;HS= HSnxt; . x=HSt; . HS=HSnxt;x=HSt; . x=HSt
9、;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)； . 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
10、) 正确答案： 30. 从一个具有 n 个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平 均比较（）个结点。. n . n/2 . (n-1)/2 . (n+1)/2 正确答案： 31. 常对数组进行的两种基本操作是（） 。 . 建立与删除 . 索引和修改 . 对数据元素的存取和修改 . 查找与索引 正确答案： 32. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用 H（K）=K %9 作为散列函数，则散列地址为 1 的元素有（ ）个. 1 . 2 . 3 . 4 正确答案： 33. 假定在一棵二叉树中，双分支结点数为 15，单分支结点数为
11、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
12、 正确答案： 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 是上的 关系有限集合。 . 算法 . 数据元素 . 数据操作 . 数据对象 正确答案： 39. 二维数组中，每个元素的长度为 3 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到 9，从 首地址 S 开始连续存放在存储器内，存放该数组至少需要的字节数是（） 。. 80 . 100 . 240 . 270 正确答案： 40. 链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之 间的逻辑顺序。 . 正确 . 错误 正确答案：
