文档介绍：共 7页第 1页《算法与数据结构》模拟试题 7答案及评分标准一、填空题(每小题 2 分,共 20 分) 1、顺序存储结构链式存储结构 2、时间复杂度空间复杂度 3、栈顶栈底 4、274 5、n2 n -1 6、存储空间的分配释放的存储空间的回收 7、以顺序方式存储结点按关键字有序 8、插入排序交换排序选择排序 9、关键字存储地址或存储地址关键字 10、索引文件散列(哈希)文件二、单项选择题(请将答案写在题目后的括号中。每题 2 分,共 18 分) 题号 123456789 答案 ADCBCDABB 三、分析题(每题 6 分,共 30 分) 1、解: 做完下列操作后队列的头尾指针的状态变化情况如下面图形所示。 1024 3 5 front rear (a) 队列初始化①a, e,b 入队 1024 3 front rear a eb5 1024 3 rear 5 b front 1024 3 front mt b5s k reart 共 7页第 2页每图 1分 2、解: ⑴该树的孩子表示法的复合链表存储结构如下图; (3分) ABC?DE?F?G?H?I?J?┇┇ 0 10 0123456789 MAX_NODE-1 root num 3? 216? 549? 87共 7页第 3页⑵将此树转换为二叉树如下图。(2分) ⑶转换后二叉树的后序遍历序列是: GFEJIHDCBA (1分) 3、解: ⑴该图的正邻接链表如下图所示: (2分) ⑵给出对该图进行拓扑排序过程如下(3分) ,其拓扑序列是:V 0→V 1→V 2→V 4→V 3→V 5(1 分) ABF C EDIJ H G V 02V 12V 23V 31V 42V 52 ∧ 012345 15 23 ∧ 26 43 ∧ 55 ∧ 34 510 ∧ 48 39 57 ∧共 7页第 4页 4、解:根据所给定的散列函数和处理冲突方法,得到的散列表结构如下: 9V 4 5 10 7 863 4V 1 V 2V 3V 59V 4 5 10 7 8 4V 2V 3V 5 ①输出 V 0后②输出 V 1后 9V 4 57 V 3V 5③输出 V 2后 5 V 3V 5④输出 V 4后 V 5④输出 V 3后 0123456789 10 ∧∧∧∧∧ 25 18 69 17 16∧ 116 ∧ 87∧ 31 29∧ 47∧ 95∧ 42 53∧共 7页第 5页 5、解:采用希尔排序法对该序列做非递减排序的每一趟结果如下。( 一趟 3 分,二趟 2分, 三趟 1分) 四、算法填空(每空 2 分,共 20 分) 请在下面各算法的空白处填上相应语句实现算法功能。每个空白处只能填一个语句。 1、设有一个以 L为头结点的双向循环链表,删除数据为 key 的所有结点。 p–>next !=Lp–> prior-> next =p –>next p->next->prior=p->prior 2 、非递归中序遍历二叉树。 s tack [++top]=p p=p->Rchild 3、二叉排序树的查找。 44 47 15 29 12 40 47 39 58 2773 44 86 55 初始关键字: 55 58 73 58 44 29 27 55 47 15 29 12 40 44 39 55 27 73 47 86 58 一趟排序