midterm exam

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1-1\n",
    "在用数组表示的循环队列中，front值一定小于等于rear值。 F (2分)\n",
    "\n",
    "1-2\n",
    "将1、2、3、4、5、6顺序插入初始为空的AVL树中，当完成这6个元素的插入后，该AVL树的先序遍历结果是：4、2、1、3、5、6。 T (3分)\n",
    "\n",
    "1-3\n",
    "无向连通图边数一定大于顶点个数减1。 F (3分)\n",
    "\n",
    "1-4\n",
    "算法分析的两个主要方面是时间复杂度和空间复杂度的分析。 T(2分)\n",
    "\n",
    "1-5\n",
    "若用链表来表示一个线性表，则表中元素的地址一定是连续的。 F(3分)\n",
    "\n",
    "1-6\n",
    "通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。 F(3分)\n",
    "\n",
    "1-7\n",
    "某二叉树的后序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无右孩子。 T(3分)\n",
    "\n",
    "1-8\n",
    "将一棵完全二叉树存于数组中（根结点的下标为1）。则下标为23和24的两个结点是兄弟。 F (3分)\n",
    "\n",
    "1-9\n",
    "如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路。 F(3分)\n",
    "\n",
    "1-10\n",
    "在一棵由包含4、5、6等等一系列整数结点构成的二叉搜索树中，如果结点4和6在树的同一层，那么可以断定结点5一定是结点4和6的父亲结点。 F (3分)\n",
    "\n",
    "2-1\n",
    "表达式a*(b+c)-d的后缀表达式是：a b c + * d - (4分)\n",
    "\n",
    "2-2\n",
    "在单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行 s->next=p->next; p->next=s;(4分)\n",
    "\n",
    "2-3\n",
    "在并查集问题中，已知集合元素0~8所以对应的父结点编号值分别是{ 1, -4, 1, 1, -3, 4, 4, 8, -2 }（注：−n表示树根且对应集合大小为n），那么将元素6和8所在的集合合并（要求必须将小集合并到大集合）后，该集合对应的树根和父结点编号值分别是多少？ (4分)\n",
    "4和-5\n",
    "\n",
    "2-4\n",
    "将{5, 2, 7, 3, 4, 1, 6}依次插入初始为空的二叉搜索树。则该树的后序遍历结果是：1, 4, 3, 2, 6, 7, 5 (4分)\n",
    "\n",
    "2-5\n",
    "对最小堆（小顶堆）{1,3,2,12,6,4,8,15,14,9,7,5,11,13,10} 进行三次删除最小元的操作后，结果序列为：4,6,5,12,7,10,8,15,14,9,13,11(4分)\n",
    "\n",
    "2-6\n",
    "三叉树中，度为1的结点有5个，度为2的结点3个，度为3的结点2个，问该树含有几个叶结点？ 8\n",
    "\n",
    "2-7\n",
    "循环顺序队列中是否可以插入下一个元素（与队头指针和队尾指针的值有关）\n",
    "\n",
    "2-9\n",
    "给定N×N的二维数组A，则在不改变数组的前提下，查找最大元素的时间复杂度是：O(N^2)(4分)\n",
    "\n",
    "2-10\n",
    "设一段文本中包含4个对象{a,b,c,d}，其出现次数相应为{4,2,5,1}，则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？ 2\n",
    "\n",
    "2-11\n",
    "具有65个结点的完全二叉树其深度为（根的深度为1）：7\n",
    "\n",
    "2-12\n",
    "下列函数中，哪个函数具有最慢的增长速度：NlogN^2(4分)\n",
    "\n",
    "N(logN)^2\n",
    "N^1.5\n",
    "NlogN^2\n",
    "N^2logN\n",
    "\n",
    "5-1\n",
    "下列代码的功能是返回带头结点的单链表L的逆转链表。\n",
    "\n",
    "List Reverse( List L )\n",
    "{\n",
    "    Position Old_head, New_head, Temp;\n",
    "    New_head = NULL;\n",
    "    Old_head = L->Next;\n",
    "\n",
    "    while ( Old_head )  {\n",
    "        Temp = Old_head->Next;\n",
    "        Old_head->Next = New_head(6分);  \n",
    "        New_head = Old_head;  \n",
    "        Old_head = Temp; \n",
    "    }\n",
    "    \n",
    "    L->Next = New_head(6分);\n",
    "    return L;\n",
    "}\n",
    "\n",
    "5-2\n",
    "下列代码的功能是从一个大顶堆H的某个指定位置p开始执行下滤。\n",
    "\n",
    "void PercolateDown( int p, PriorityQueue H )\n",
    "{\n",
    "   int  child;\n",
    "   ElementType  Tmp = H->Elements[p];\n",
    "   for ( ; p * 2 <= H->Size; p = child ) {\n",
    "      child = p * 2;\n",
    "      if ( child!=H->Size && H->Elements[child+1] > H->Elements[child](6分) )\n",
    "         child++;\n",
    "      if ( H->Elements[child] > Tmp )\n",
    "         H->Elements[p] = H->Elements[child](6分);\n",
    "      else  break;\n",
    "   }\n",
    "   H->Elements[p] = Tmp; \n",
    "}"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}