： 名 姓线 ： 号 学 订 1 9 0 2 ： 级 班 机 算装 计 ： 业 专 装 沈阳工业大学北重函授站 2009-2010学年第2学期期末考试 《 数据结构 》试题（A） 题号 一 二 三 四 五 六 总分 得分 一、填空题：（本大题共8小题，每题1分，共15分） 1._________是描述数据的基本单位，_________是描述数据的最小单位。 2.在算法设计时应该考虑的5 个方面分别是________、_______、_______、_______、 ______。 3．数据结构的逻辑结构具有_________和________两种结构。 4. 数组A[4][5]的下标下界为0，每个元素占4个字节，存储在起始地址为1000的连续内 存单元，则元素A[2][3]的地址为_________。 5. 栈的特点是 ，队列的特点是 。 6. 树中没有父结点的结点称为 结点。 7. 向一个长度为n的向量的第i个元素（1≤i≤n）之前插入一个元素时，需向后移动 个元素。 8．有向图的边也称为 。 二、选择题：（本大题共5小题，每题2分，共10分。在每小题给出的四个选择中，只有 一项是符合题目要求的，把所选择项前的字母填在题后的括号内。） 1.在一个单链表中，已知q结点是p结点的前驱结点，。若在q和p之间插入s结点，则 执行（） A、s->next=p->next；p->next=s；B、p->next=s->next；s->next=p； C、q->next=s;s->next=p； D、p->next=s；s->next=q； 2.若线性表采用链式存储，则表中各元素的存储地址（） A、必须是连续的 B、部分地址是连续的 C、一定是不连续的 D、不一定是连续的 3. 深度为k的二叉树所含叶子的个数最多为（）。 A、2k+1 B、2k-1 C、2k-1 D、2k+1 4. 对特殊矩阵采用压缩存储的目的主要为了（） A、减少不必要的存储空间 B、去掉矩阵中的多余元素 C、表达变得简单 D、对矩阵元素的存取变得简单 5. 有n个顶点的连通图G的最小生成树有（）条边。 A、n-1 B、n C、n+1 D、不确定 三、判断题：（本大题共5小题，每题2分，共10分） 1．压缩存储的三角矩阵和对称矩阵的存储空间相同（） 2．算法的时间复杂度都要通过算法中的基本语句的执行次数来确定（） 3．因为栈是一种线性表，所以线性表的所有操作都适用于栈（） 4．任意一无向连通图的最小生成树是惟一的（） 5．关键路径是从源点到汇点的最短路径（） 第1页 本试卷共4页 四、简答题：（本大题共5小题，每题10分，共65分） 1．简述什么时候用顺序表，什么时候用链表存储？ 2．什么是满二叉树和完全二叉树？ 3．简述栈的特点及与一般线性表的区别。 4．简述顺序栈可以进栈和出栈的条件。 5．已知广义表LS=（a,(b,c,d),e），写出此表的长度、深度、表头和表尾。 6． 3个结点可以组成哪几种形态的二叉树。 7．已知某系统在通信联络中只可能出现8个字符，其出现的权值是（5，29，7，8，14，23，3，11），构造一个哈夫曼树，并为这8个字符设计哈夫曼编码。 8．已知遍历某二叉树后的中根遍历序列CDBAFGEIHJ和后根遍历序列为DCBGFIJHEA，试画出此二叉树。 9．对图所示的连通图，请用prim算法构造其最小生成树。 6 V1 5 V2 5 1 5 V4 V3 3 6 4 2 （注：附答题纸1张） V5 V6 6 第2页 本试卷共4页 本文来源：https://www.wddqw.com/doc/cb81f83b83c4bb4cf7ecd132.html