《《精编》《数据结构》期中考题》由会员分享，可在线阅读，更多相关《《精编》《数据结构》期中考题（8页珍藏版）》请在金锄头文库上搜索。
1、 沈阳工程学院数据结构期中考试试题班级： 专业： 学号： 姓名： 考试日期：2008年10月10日一、 选择题（2分8 = 16分）1. 以下数据结构中，是非线性数据结构的是 。 A. 树 B. 字符串 C. 数组 D. 栈2. 下列程序段的渐进时间复杂度为 。 for( int i=1;i=n;i+) for( int j=1;jnext=s;s-next=p-next; B s-next=p-next;p-next=s;Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s;7. 先序遍历序列与中序遍历序列相同的二叉树为 。 A. 根结点无左子树
2、的二叉树 B.根结点无右子树的二叉树C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树8. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 二、 填空题（2分5 =10分）1. 一个算法具有5个特性： 、 、 、有零个或多个输入，一个或多个输出。2. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 存储结构。3. 字符串“abcd
3、”中共有 个长度大于0的字串。4. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是 。5. 具有n个结点的完全二叉树的高度为 三、 名词解释（24分）（1）栈与队列 （2）完全二叉树 （3）数据的逻辑与存储结构四、 简答题（30分）1. 请对线性表进行顺序存储和链式存储的特点作比较。2. 假设有一个适当大小的栈S，输入栈的序列为A，B，C，D，E。问：（1）能否得到下列的输出序列： B，C，D，E，A； E，A，B，C，D；E，D，C，B，A。（2）写出所有可能正确的输出序列。3. 设一棵二叉树后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，
4、要求： （1）画出该二叉树； （2）写出该二叉树的先序遍历序列；五、 算法设计题（20分）1. 填充下列算法的空白处，完成在不带表头结点的单链表第i个结点之前插入新元素x的操作。（8分）int Insert ( const int x, const int i ) /在链表第 i 个结点处插入新元素 x listNode *p = first; int k = 0; while ( p != NULL & k i -1 ) ; k+; /找第i-1个结点 if ( p = NULL & first != NULL ) /非空表且链短，找不到i-1个节点 cout “Invalid positi
5、on for Insertation!n”; return 0; listNode *newnode= new Node(x, NULL); if ( first = NULL | i = 0 ) /插入空表或插在非空表前 newnodelink = first; if ( first = NULL ) last = newnode; ; / 修改首指针 else /插在表中或末尾 ; if ( plink = NULL ) last = newnode; ; return 1;/正常插入，函数返回1 2. 若用二叉链表作为二叉树的存储表示，试针对下列问题编写递归算法（12分）： （1）统计二叉树中叶子结点的个数； （2）交换每个结点的左子女和右子女。选做题（20分）（西安电子科技大学2006年硕士研究生入学考试最后一题）假设以数组seq0m-1存放循环队列中的元素，同时设变量rear和quelen分别指示循环队列中的队尾元素的位置和内含元素的个数。请给出：（1）给出循环队列的队满条件和队空条件；（2）写出相应的入队列和出队列的算法，并分别分析其时间代价；（3）如果用数组sequmn来存放循环队列中的元素，则（2）中的入队列和出队列的算法中的哪些语句要修改？如何修改？
