数据结构C++模拟卷子1

1、第 1 题.( 复合题 共计 20 分) 选择题第 1.1 题.(主观 题 5 分) 数据的逻辑结构用二元组表示为：B=(K,R);K=K1,K2,K3,K4,K5,K6;R=<K2,K3>,<K3,K1>,<K1,K5>,<K5,K4>,<K4,K6>这组数据的逻辑结构是（A），开始结点是（B），终端结点是（C）。顺序方式存储这批数据时称为（D），链式存储时称为（E）。如果对其操作加以限制，只能在一端插入和删除元素，则此时可称该结构为（F）；规定只能在一端插入元素和在另一端删除元素，则该结构又称为（G）。A、线性结构 非线性结构 图

2、 树B、K1 K2 K5 K4C、K2 K3 K4 K6D、散列表 链表 顺序表 有序表E、散列表 链表 顺序表 有序表F、队列 栈 双端栈 堆G、队列 栈 双端栈 堆参考答案A、线性结构 B、K2 C、K6 D、顺序表 E、链表 F、栈 G、队列第 1.2 题.(客观 单选题 5 分) 执行下列程序段时，S语句执行的次数为：for (int k=1; k<=n; k+)for (int j=1; j<=k; j+) S;（n2）（n2/2）n(n+1)n(n+1)/2第 1.3 题.(客观 单选题 5 分) 在一个长度为N的顺序表中删除第m个元素（1mN）时，需向前移动的元素个数

3、是：NmN-mN-m-1第 1.4 题.(客观 单选题 5 分) 存储密度是指存储空间的利用率，即用于存储数据信息的存储量与整个结构所占总存储量之比。在下列结构中，存储密度为1的结构是：顺序表（向量）单链表散列表二叉链表第 2 题.( 复合题 共计 20 分) 简答题第 2.1 题.(主观 题 5 分) 对规模为N的数据进行排序，各种算法的时间复杂度均是N的函数。在已经学习的排序算法中，列举出时间复杂度分别为 N2 和 Nlog2N 的排序算法各两种，并对时间复杂度为Nlog2N的两种排序算法的空间复杂度进行比较。参考答案插入、选择、起泡：O(N2)快速、二路归并排序：O(Nlog2N)快速排

4、序的空间复杂度O(Nlog2N)二路归并排序的空间复杂度O(N)第 2.2 题.(主观 题 5 分) 对规模为N的数据使用二分法检索，请说明检索的时间复杂度及该算法对数据结构的要求。参考答案二分法检索的时间复杂度O(log2N),要求数据结构是有序的顺序表。第 2.3 题.(主观 题 5 分) 已知二叉树的前序遍历序列是abdgcefh，中序遍历序列是dgbaechf，请画图表示该二叉树，并写出它的后序遍历序列。参考答案gdbehfca第 2.4 题.(主观 题 5 分) 一个有向带权图的邻接矩阵如下，用Floyd算法求解各顶点间最短路径，请写出能表示各顶点间最短路径的最终邻接矩阵。并写出初始

5、路径矩阵及求解过程的路径记录矩阵，并请说明Floyd算法的求解算法策略属于哪一类方法。0 4 116 0 23 0参考答案最终结果相阾矩阵：0 4 65 0 23 7 0路径矩阵：0 0 01 1 12 -1 20 0 01 1 12 0 20 0 11 1 12 0 20 0 12 1 12 0 2算法策略：动态规划第 3 题.( 复合题 共计 30 分) 算法理解第 3.1 题.(主观 题 6 分)已知带头结点的单链表类模板定义如课本。请说明下列算法的功能。对于数据序列93，100，5，102，19，21，86，27，经过下列算法处理后，得到的数据集合是什么？template void L

6、inkList:process() LinkNode*p = head->next, *q; while (p) q = p->next ; delete p; p = q; tail = head; head->next = NULL; len = 0; 参考答案清除带头结点的单链表中的数据结点。处理结果的数据集合是空集第 3.2 题.(主观 题 6 分) 已知顺序表类模板定义如课本。请说明下列算法的功能是什么？对于数据序列93，100，5，102，19，21，86，27，分别用不同实参调用下列算法时，返回值分别是什么？（1）实参是19（2）实参是80template in

7、t SqList:LocateElem(const ElemType &e) const ElemType *p = elem; int i = 1; while( i <= len && *p != e) p+; i+; if (i <= len) return i; return 0; 参考答案在顺序表中查找实参e是否存在，如果存在，返回e所在位置，如果不存在，返回 0。（1）返回5（2）返回0第 3.3 题.(主观 题 6 分) 已知带头结点的单链表类模板定义如课本，下列算法是其成员函数之一。请问：（1）调用该函数时，需要实参数据几个？e有什么作用？i

8、又有什么作用？（2）该函数的返回值有哪几种？每种返回值都代表什么意义？（3）对于数据序列93，100，5，102，19，21，86，27,当实参i是6时，该函数调用后能够得到哪些信息（数据）？分别表示什么？当实参i是10时，该函数调用后又能够得到哪些信息（数据）？分别表示什么？template bool LinkList:GetElem(ElemType &e, int i) const if (i < 1 | i > len) return false; LinkNode*p = head->next; int k = 1; while (k < i) p =

9、 p->next; k+; e = p->data; return true; 参考答案（1）调用该函数时，需要实参数据2个。查找成功时，e用于存储数据序列中第i个数据的值。i表示要查找的数据所在的位置。（2）该函数的返回值有两种：true和false，true表示查找成功，false表示查找失败。（3）对于数据序列93，100，5，102，19，21，86，27,当实参i是6时，该函数调用后能够得到两个信息，一个是查找成功的标志返回值true，另一个是在数据序列的第6个位置里面的数据21。当实参i是10时，该函数调用后只能够得到返回值false，表示查找不成功。第 3.4 题.(

10、主观 题 6 分) 请说明一个顺序表v经过下列函数处理后，其数据排列上有何特点，并写出该结果序列。设v=16,12,30,28,2,10,20,6,18templateint process(ElemType v , int low , int high) ElemType pivot = vlow; while (low < high) while (low < high && vhigh >= pivot) high-; vlow = vhigh; while (low < high && pivot >= vlow) low+

11、; vhigh = vlow; vlow = pivot; return low;参考答案处理后v的排列为：6，12，10，2，16，28，20，30，18。以16为标准把数据进行一次划分，16前的元素都比16小，16后的元素比16大。第 3.5 题.(主观 题 6 分) 二叉树及队列定义如课本，请说明下列函数的功能。template void BinaryTree:process(void (*visit)(const ElemType &e) queue*> Q; if (m_root) Q.push (m_root); while (!Q.empty () BTNode*p

12、; p = Q.front (); Q.pop (); visit (p->data); if (p->lchild) Q.push (p->lchild); if (p->rchild) Q.push (p->rchild); 参考答案按层次遍历并输出二叉树的结点第 4 题.( 复合题 共计 30 分) 算法设计2001第 4.1 题.(主观 题 10 分) 栈是一种常用的数据结构，以下是顺序栈SqStack的定义。请写出这个栈的成员函数的实现。template <class ElemType> / 声明一个类模板class SqStack / 顺序

13、栈类public: SqStack(int m); / 构造函数 SqStack(); / 析构函数 void Clear(); / 清空栈 bool Empty() const; / 判栈空 int Length() const; / 求长度 ElemType & Top() const; / 取栈顶元素 void Push(const ElemType &e); / 入栈 void Pop(); / 出栈private: ElemType *m_base; / 基地址指针 int m_top; / 栈顶指针 int m_size; / 向量空间大小;参考答案/ 构造函数，分

14、配m个结点的顺序空间，构造一个空的顺序栈template <class ElemType>SqStack <ElemType>:SqStack(int m) m_top = 0; m_base = new ElemTypem; m_size = m;/ 析构函数，将栈结构销毁template <class ElemType>SqStack <ElemType>:SqStack() if (m_base != NULL) delete m_base;/ 清空栈template <class ElemType>void SqStack &

15、lt;ElemType>:Clear() m_top = 0;/ 若栈为空，则返回true，否则返回falsetemplate <class ElemType>bool SqStack <ElemType>:Empty() const return m_top = 0;/ 求栈中元素的个数template <class ElemType>int SqStack <ElemType>:Length() const return m_top;/ 取栈顶元素的值。先决条件是栈不空template <class ElemType>Ele

16、mType & SqStack <ElemType>:Top() const return m_basem_top - 1;/ 入栈，若栈满，则先扩展空间。插入e到栈顶template <class ElemType>void SqStack <ElemType>:Push(const ElemType &e) if (m_top >= m_size) / 若栈满，则扩展空间 ElemType *newbase; newbase = new ElemTypem_size + 10; / 扩大10个元素空间 for(int j = 0;

17、j < m_top; j+) / 复制元素到新空间 newbasej = m_basej; delete m_base; / 释放原空间 m_base = newbase; / 重置基地址 m_size += 10; m_basem_top+ = e;/ 出栈，弹出栈顶元素。先决条件是栈不空template <class ElemType>void SqStack <ElemType>:Pop() m_top-;第 4.2 题.(主观 题 10 分) 已知有一带头结点的单链表，请写出操作Append的实现，该操作是在单链表的最后插入一个值为e的结点。函数原型：vo

18、id bool LinkList<ElemType>:Append(const ElemType &e);参考答案/ 在链表linkList的末尾插入新的元素etemplate<class ElemType>bool LinkList<ElemType>:Append(const ElemType &e) LinkNode<ElemType> *q; q = new LinkNode<ElemType> ; q->data = e; tail->next = q; / 尾部插入q结点 tail = q; tail->next = NULL; +len; / 表长增1 return true;第 4.3 题.(主观 题 10 分) 已知二叉排序树类定义如课本，下列