C++数据结构练习试题

期 中 数据结构 试题(网大)
班级	学号	姓名	得分
题号 一 二 三 四 五 六 七 八 九 十 分数
一、解答下列各题（每题6分 共30分）
1. 设有长度为10的字符串：3*-y-a/y^2，试利用栈，将该字符串的次序改为：3y-*ay2^/-。请列出进/出栈操作的操作序列。可用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取一个字符加到新字符串尾的出栈操作。例如ABC变为BCA的操作序列为XXSXSS。
2．已知稀疏矩阵如下，给出它的按行优先方式的三元组表示。
450){this.resized=true;this.style.width=450;}”>
3．已知主串为’abcabcabba’，模式串为’cab’。试给出使用简单匹配算法进行模式匹配的各趟匹配结果。
4．画出具有四个结点，高度为3的所有二叉树形，并指出其中哪些是完全二叉树。
5．设有树如下图所示，请画出其对应的二叉树。
450){this.resized=true;this.style.width=450;}”>
二、解答下列各题（每题8分，共40分）
1． 已知对某二叉树的先序和中序遍历的序列分别为：AFEGCBD和EFGCADB，试画出该二叉树的逻辑结构，并求其后序遍历的结点序列。
2. 设有关键字序列：18，22，32，45，47，51，77，83，86。现采用对半搜索方法分别查找关键字45和48，则在算法执行中，它们分别与序列中哪些元素进行比较，请将与之比较的元素依次填入下表中
1 2 3 4 5 搜索45           搜索48
3．设有优先权队列：22，36，28，45，41，31，47，66，现在该优先权队列中插入新元素29，给出插入操作完成后的结果。再从插入后的队列中删除一个元素，给出删除操作完成后的结果。
1 2 3 4 5 6 7 8 9 初始队列 22 36 28 45 41 31 47 66   插入后                   删除后
4．设有权值W={3，4，6，8，11，13}，试构造一棵哈夫曼树，并计算该树的带权路径长度。
5．设有二叉树如下图所示。现采用二叉链表表示法存储之。请分别画该存储表示方式的示意图。
450){this.resized=true;this.style.width=450;}”>
三、算法理解（共18分）
1. 阅读下列顺序表类的成员函数Search，
（1） 说明此函数的功能。
（2） 分别说明执行下列语句的结果：
cout<<l.Search(19); 　　　　　cout<<l.Search(23);
其中，l是数据元素为整数的顺序表对象，它包括线性表（22，20，17，23，33，21）。
template<class T> 　　int SeqList<T>::Search(const T& x) const 　　{ 　　　for (int i=0;i<length;i++) 　　　if (elements[i]==x) return ++i; 　　　return 0; 　　}
2. 阅读下列单链表类的成员函数Y，
（1） 说明此函数实现是针对何种单链表设计：不带表头结点的单链表、带表头结点的单链表、　　　单循环链表？
（2） 分别说明执行下列语句的结果：
cout<<l.Y(19); 　　　　　 cout<<l.Y(23);
其中，l是数据元素为整数的上述链表对象，它包括线性表（22，20，17，23，33，21）。
template<class T> 　　int SingleList<T>::Y(const T& x)const 　　{ 　　　Node<T> *p=first; 　　　for (int i=1; p && p->data!=x; i++) p=p->link; 　　　if (p) return i; 　　　return 0; 　　}
3． 阅读下列二叉树类上的成员函数Z
（1） 说明其功能。
（2） 说明执行下列语句的结果:
cout<<x.E1()<<endl;
设x是二叉树对象，它包括一棵如下的二叉树。
450){this.resized=true;this.style.width=450;}”>
template <class T> 　　void BTree<T>::E1() 　　{ 　　　　E(root); 　　} 　　template <class T> 　　void BTree<T>::E(BTNode<T> *p) 　　{ 　　　if (p){ 　　　　BTNode<T> *q=p->lchild; 　　　　p->lchild=p->rchild; 　　　　p->rchild=q; 　　　　E(p->lchild); 　　　　E(p->rchild); 　　　} 　　}
四、算法填空（每空1分，共12分）
1. 双向链表结点类的定义如下
template <class T> 　　　　　　　　　　//声明DNode类 　　class DNode 　　{ 　　　private: 　　　T data; 　　　DNode<T> *llink, *rlink; 　　};
请补充完整下面在双向链表中在指针p所指示的结点前插入一个新元素x的程序段。
DNode<T> * q=   ; 　　q->data=x; 　　q->llink=   ; 　　q->rlink=   ; 　　  ; 　　p->llink=q;
2． 请补充完整下面顺序堆栈的插入和删除操作函数，其中top为栈顶指针。
template<class T> 　　void SeqStack<T>::Push(const T &x) 　　{ 　　　assert(!IsFull()); 　　　s[    ]=x; 　　} 　　template<class T> 　　void SeqStack<T>::Pop() 　　{　　 　　　assert(!IsEmpty()); 　　　  ; 　　}
3． 请补充完整下面循环队列的判空和判满操作函数，其中front和rear分别为队头和队尾指针　　　　MaxSize为队列的最大允许长度。
template <class T> 　　bool SeqQueue<T>::IsEmpty() const 　　{ 　　　  ; 　　} 　　template <class T> 　　bool SeqQueue<T>::IsFull() const 　　{ 　　　return    ; 　　}
4．请补充完整下面二叉树的先序遍历函数。
template <class T> 　　void BTree<T>::PreOrder(void (*Visit)(BTNode<T>* u), 　　BTNode<T>* t) 　　{ 　　　if (t){ 　　　Visit(t); 　　　  ; 　　　  ; 　　　} 　　}
5.请在下面顺序表的C++类定义的下划线处填上适当的语句。元素被保存在动态一维数组　　　　　　elements中（省略号…处不必补上。）
template <class T> 　　class SeqList:public LinearList<T> 　　{ 　　　public: 　　　SeqList(int MaxListSize); 　　　~SeqList() { delete   ; }; 　　　… 　　　private: 　　　int length; 　　　int MaxLength; 　　　  ; 　　}