天津工业大学算法与数据结构考试试卷及参考答案1
一、单项选择题（5’）
1．下列关于线性表的叙述中正确的是（）。
A、线性表的逻辑顺序与物理顺序总是一致的         
B、线性表的顺序存储表示优于链式存储表示         
C、线性表若采用链式存储表示时所有存储单元的地址可连续或可不连续       
D、每种数据结构都应具备三种基本运算：插入、删除和查
答案：C
2．对一个初始为空的栈S执行操作S.Push（5），S.Push（2），S.Push（4），S.Pop（x），S.getTop（x）后，x的值应是（）。
A、5                                     
B、2             
C、4                                   
D、0
答案：B
3. 将递归算法转换成对应的非递归算法时，除了单向递归和尾递归的情况外，通常需要使用（）保存中间结果。
A、链表                                 
B、栈             
C、队列                                   
D、顺序表
答案：B
4. 算法的时间复杂度的表示方法是：（）。
A、实现算法的程序在指定机器上执行的时间
B、标准程序在机器上的执行时间
C、基本操作重复次数，即问题规模n的某个函数
D、与刻画基本操作重复次数的函数同阶无穷大的函数f(n)
答案：D
5. 在树中，树的度与结点的度之间的关系是：（）。
A、树的度就是结点的度
B、树的度为2，结点的度可以是0，1和2
C、结点度中最大值为树的度
D、树的度与结点的度无关
答案：C
6. 用链接方式存储的队列，在进行插入运算时：
A、仅修改头指针 头、尾指针都要修改
B、头、尾指针都要修改
C、仅修改尾指针
D、头、尾指针可能都要修改
答案：D
7. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10) ，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
A、688
B、678
C、692
D、696
答案：C
8. 最好情况下插入排序的比较次数是：（）。
A、O(n)
B、n
C、n-1
D、O(n*n)
答案：C
二、多项选择题（5’）
1. 以下程序段的完成的功能是(): /* head 是指向由data和link两个域的结点构成的单向链表头 */ P = head; While ( p != NULL) { Printf(p->data); P = p->link; }
A、对链表的遍历
B、输出了链表中所有数据信息
C、没有功能，因为只是输出与循环
D、输出了除表头结之外的所有结点信息
答案：AB
2. 数据是信息的载体，它有以下几种形式():
A、整数和实型数
B、字符串
C、图像和声音
D、信息
E、磁盘文件
答案：ABC
3. 一维数组元素的类型可以是():
A、简单变量，如整数、浮点数
B、复合变量，如结构体，数组
C、只有简单变量
D、指针变量
E、字符串
答案：ABD
4.在算法分析与数据结构中，算法描述方法有():
A、自然语言
B、框图
C、类计算机语言
D、数据结构
答案：ABC
5. 一棵含有25个结点的完全二叉树的深度是多少():
A、4
B、5
C、6
D、log225
答案：AD
二、判断题（5’）
1. 数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。
答案：错误
2. 顺序存储方式只能用于存储线性结构。
答案：错误
3. 任意图都是其自身的子图。
答案：正确
4. 如果图中有一部分边的权为负值，那么用Dijkstra 算法求图的最短路径是可行的。
答案：错误
5. 线性表中的元素只能是简单类型。
答案：错误
6. 线性表是数组。
答案：错误
7. 指针就是地址，有人在数组中采用指示下标值的方法实现单向链表。另外的人说这不是链表结构，他的说法对吗？
答案：错误
8. 栈满是数据对象栈的固有操作。
答案：错误
9. 在求最短路径的Dijkstra算法和Floyd算法中，Dijkstra算法只能求从一点到其他各点的最短路径，而Floyd算法可以求图中两两点之间的最短路径。
答案：错误
填空题（5’）
1. 栈只能在      插入和删除元素；对于队列只能在      插入和      删除元素。
答案：栈顶；队尾；队首
2. 一棵具有257个结点的完全二叉树，它的深度为      。
答案：9
3. 在一个顺序栈中，若栈顶指针等于      ，则为空栈；若栈顶指针等于      ，则为满栈。
答案：-1，maxSize-1
简答题（20’）
1. 数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、队列、优先级队列等；非线性结构包括树、图等。这两类结构各自的特点是什么？
答案：线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成
数据结构与算法题库
员和一个终端成员，并且所有数据成员都最多有一个直接前驱和一个直接后继。
非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。
2. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
答案：DLR： A B D F J G K C E H I L M
      LDR:  B F J D G K A C H E L I M
      LRD： J F K G D B H L M I E C A
3．如果一棵有n个结点的满二叉树的深度为d（树根所在的层次为1），则给出推导式：
（1）用深度d表达其结点总数n。
（2）用结点总数n表达深度d。
（3）若对该树的结点从1开始按中序遍历次序进行编号，则树根结点的编号如何用d表示？树根结点的左子女结点的编号如何用d表示？右子女结点的编号如何用d表示？
答案：
（1）对于深度为d的满二叉树，结点个数为n=2d-1。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。