系别 班次 学号 姓名 第 1 页 共 14页 ××科技大学成都学院二零零八至二零零九学年第一学期 数据结构 课堂测试（60 分钟） 闭卷 考试时间： 题号 一 二 三 总分 评卷教师 分数 一．填空题（每空 2 分，共 40 分）； 1. 数据结构算法中，通常用时间复杂度和__空间复杂度___两种方法衡量其效率。 2. 下面程序段的时间复杂度为___O(n2)______。(n>1) for(i = 1; i <= n; i++) for(j = 1; j <= i; j++) x = x + 1; 3. 静态链表中指针表示的是______下一结点的地址______。 4. 线型表、栈和队列都是____线型_______结构，可以在线型表的____任意___位置插入和删除元素；对于栈只能在____栈顶_____插入和删除元素；对于队列只能在____队尾___插入元素和_____队头_____删除元素。 5. 在具有 n 个单元的循环队列中，队满时共有_____n-1____个元素。 6. 在一个长度为 n 的顺序表中第i 个元素（1<=i<=n）之前插入一个元素时，需向后移动__n-i+1__个元素。 7. 在 n 个结点的单链表中要删除已知结点*p，需找到它的_____前驱________。 8. 带有一个头结点的单链表 head 为空的条件是_________head->next= =NULL__________。 9. 在栈顶指针为 hs 的链栈中，判断栈空的条件是_________hs= =NULL__________。 10. 在 hq 的链队列中，判定只有一个结点的条件是__hq.front->next==hq.rear________。 11. 非空的循环单链表 head 的尾结点（由p 指向），满足条件____p->next==head。 12. 两个串相等的充分必要条件是______串长相等且对应字符相等_______。 13. 空串是_______长度为 0 的串______，其长度等于___0________。 14. 空格串是______由空格字符组成的串______， 其长度等于_____空格的个数_________ 。 二．单项选择题（每题 2 分，共 30 分）；（说明：请将答案填入下表中） 题号 1 2 3 4 5 6 7 8 9 10 答案 A A B B D B C B B C 题号 11 12 13 14 15 答案 A A C D D 1. 若某 线性 表最 常用的操 作 是存 取 任一指定序号的元素和在最 后进 行 插入和删除运算，则 利 用（A）存 储 方式 最 节 省 时间。 A． 顺序表 B． 双 链表 C． 带头结点的双 循环链表 D． 单循环链表 2. 设 a1、a2、a3 为 3 个结点，则 如 下的链式 存 储 结构称 为：A 系别 班次 学号 姓名...
