数据结构-A卷-软件0811_0812-2010年-集美大学试卷纸(包括答题纸

1、集 美 大 学 试 卷 纸 2009 2010 学年 第 二 学期课程名称数据结构试卷卷别A卷适 用学院、专业、年级计算机工程学院 软件工程专业 08级考试方式闭卷 开卷 备注总分题号一二 三四五 六得分阅卷人得分一、 选择题(共10分)。【1】【2】【3【4】【5】【6】【7】【8】【9】【10】1、（1分）每一个结点只存储个数据元素，各结点存储在连续的存储空间，该存储方式是【1】存储方式。CA. 索引B.散列C.顺序D.链式2、（1分）下列算法的时间复杂度是【2】Dfor(i=0;in;i+)for(j=0;j isp(op)，令ch进栈，读入下一个字符ch。若 icp(ch) isp(o

2、p)，退栈并输出。若 icp(ch) = isp(op)，退栈但不输出，若退出的是“(”号读入下一个字符ch。算法结束，输出序列即为所需的后缀表达式。解答：（1） （10分）(2) icp和isp的含义； （2分）icp isp (3)转换得到的后缀表达式是： （1分）8、（共4分）时间复杂度的度量方法之一是插入计数变量count，请在下面的的函数中填空插入变量count以计算程序每一步的步数；并给出该程序总的步数。 假设count初值为0，加入count计数后求累加和的函数：float sum (float a , int n) float s = 0.0; count+; /计算上面的赋值

3、语句的步数 for (int i = 0; i n; i+) ; /计算上面的for 语句的步数 s = s + ai; ; /计算上面的赋值语句的步数 ; /计算上面的for 的最后一次步数return s;count+; /计算上面的 return 语句的步数 /上述程序总的步数 count = 求累加和的函数 float sum (float a , int n) float s = 0.0; for (int i = 0; i item; if (item != ) /不是字符串结束标志- if (item != #) /是字符串中的字符 subTree = new BinTreeNo

4、de(item); /建立根结点 if (subTree = = NULL) cerr “存储分配错!” leftChild); /递归建立左子树CreateBinTree (in, subTree-rightChild); /递归建立右子树 else subTree = NULL; /封闭指向空子树的指针 main()函数如下：int main()BinTreeNode myBTN; /声明一个二叉树结点类的实例myBTNistream myin; /声明一个输入流对象的实例myinCreateBinTree (myin,myBTN); return 0; /main()正常结束返回0如果上

5、述程序运行时从键盘输入AB#D#C#，请画出生成的二叉链表形式的二叉树（2分）；分析并画出调用CreateBinTree (myin,myBTN)递归程序的递归展开和递归返回过程（6分）；给出上述生成的链表形式的二叉树的后序线索二叉树（请在图上标注清楚后序前驱线索和后序后继线索）（2分）。 解答：生成的二叉链表形式的二叉树是： （2分）调用CreateBinTree (myin,myBTN)递归程序的递归展开和递归返回过程 （6分）后序线索二叉树是： （2分）3、（共10分）下图对应的链式栈的类定义如下： （1）请找出该类及相关的成员变量，说明每一个成员变量的含义； （3分）（2）给出成员函数

6、Pop(char& x)、getTop(char& x)的实现； （5分）注意：成员函数实现的书写规范。（3）代码中有两个地方出现关键字const，请问有何用途？那么关键字NULL又表示什么？（2分） struct StackNode /栈结点类定义private: char data; StackNode *link; public: StackNode(char d = 0, StackNode *next = NULL) : data(d), link(next) ; class LinkedStack /链式栈类定义 private: StackNode *top; public: LinkedStack() : top(NULL) LinkedStack() makeEmpty(); void Push(char x); /变量x值入栈 bool Pop(char& x); /栈