资源描述：
《数据结构考试试题一及参考答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、课程名称：数据结构考试时间：姓名：班级：学号：一、选择题（每题2分，共20分）（）1、二叉树是非线性数据结构，所以__________。Ａ）顺序存储结构和链式存储结构都能存储;Ｂ）它不能用链式存储结构存储;Ｃ）它不能用顺序存储结构存储;Ｄ）顺序存储结构和链式存储结构都不能使用（）2、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为__________。A）随机存储结构B）逻辑结构C）顺序存储结构D）链式存储结构（）3、判定一个栈ST（最多元素为m0）为空的条件是__________。A）ST->top<>0B）ST->top=
2、0C）ST->top<>m0D）ST->top=m0A．0243156B.0136542C.0361542D.0134256（）4、已知图的邻接矩阵如下，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是_______。（）5、用5个权值{3,2,4,5,1}构造的哈夫曼（Huffman）树的带权路径长度是A）32B）33C）34D）15（）6、给定二叉树的两种遍历序列，分别是：先序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F；则其后序遍历序列为__________。A）BHECGIFADB）B
3、HECIGADFC）BHECIGFADD）CHEBIGADF（）7、有8个结点的有向图最多有___________条边。A）56B）28C）14D）112（）8、对22个记录的有序表作折半查找，当查找失败时，至少需要比较___________次关键字。A）3B）4C）5D）6（）9、对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。Ａ）从小到大排列好的Ｂ）从大到小排列好的Ｃ）元素无序Ｄ）元素基本有序（）10、下列排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为
4、_________。Ａ）希尔排序Ｂ）冒泡排序Ｃ）选择排序Ｄ）插入排序二、填空题（每空2分，共20分）1、在线性结构中，第一个结点前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点后续结点，其余每个结点有且只有1个后续结点。2、线性表、栈和队列都是结构，可以在线性表的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入和删除元素。3、设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底(注意!)，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值___________；从栈中弹出（
5、POP）一个元素时，变量T的值____________。4、由３个结点所构成的二叉树有___________种形态。三、算法阅读理解题（每题10分，共30分）1、分析并写出下列程序段的输出结果（队列中的元素类型为char）。voidmain(){QueueQ;//Queue表示队列InitQueue(Q);Charx=’e’,y=’c’;EnQueue(Q,’h’);//EnQueue表示入队操作EnQueue(Q,’r’);EnQueue(Q,y);DeQueue(Q,x);//DeQueue表示出队操作EnQueue(Q,x);DeQueue(
6、Q,x);EnQueue(Q,’a’);while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};Printf(x);}2、设如下图所示的二叉树BTREE的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，对二叉树BTREE，执行算法traversal(root)，试分析算法作用并指出算法执行后的输出结果。树的结点类型定义如下：structnode{chardata;structnode*lchil
7、d,rchild;};所用算法如下：voidtraversal(structnode*root){if(root){printf(“%c”,root->data);traversal(root->lchild);printf(“%c”,root->data);traversal(root->rchild);}}ABDCFGE3、下面程序实现了对输入数据进行直接插入排序的过程，并输出排序后的结果请在____________处给出所缺失的内容。typedefstruct{Intkey;intother_data;}RecordType;voidInsS
8、ort(RecordTyper[],intlength)/*对记录数组r做直接插入排序，length为数组中待排序记录的数
