发布时间 : 星期五 文章《数据结构》期终考试试卷(A)-清华大学更新完毕开始阅读
Hash(key) = key % 113 (注：117不是质数，117 = 9 * 13)
四、算法设计题（每小题5分，共15分）
设中序线索化二叉树的类声明如下：
template
ThreadNode
//其他公共成员函数 ……
private:
ThreadNode
试依据上述类声明，分别编写下面的函数。
(1) ThreadNode
//寻找以p为根指针的中序线索化二叉树在前序下的第一个结点。 (2) ThreadNode
//寻找结点*p的在中序线索化二叉树中前序下的后继结点。 (3) void preorder (inOrderThreadTree
//应用以上两个操作，在中序线索化二叉树上做前序遍历。
//树的根指针
//中序线索化二叉树类
template
//中序线索化二叉树的结点类 //线索标志 //线索或子女指针 //结点中所包含的数据
int leftThread, rightThread; Type data; };
ThreadNode
四、算法设计题（每小题5分，共15分）
(1) tamplate
ThreadNode
return p;
}
(2) template
5
ThreadNode
(3) template
void preorder ( inOrderThreadTree
}
ThreadNode
cout << p->data << endl; p = getPreorderNext ( p );
if ( p->leftThread == 0 ) return p->leftChild; if (p->rightThread == 0 ) return p->rightChild;
while ( p->rightThread != 0 && p->rightChild != NULL )
p = p->rightChild; return p->rightChild;
五、算法分析题（每小题5分，共15分）
下面给出一个排序算法，其中n是数组A[ ]中元素总数。
template
int d = 1, j;
while ( d < n /3 ) d = 3*d+1;
while ( d > 0 ) {
for ( int i = d; i < n; i++ ) {
Type temp = a[i];
j = i;
while ( j >= d && a[j-d] > temp ) { a[j] = a[j-d]; j -= d; }
a[j] = temp; } d /= 3;
} }
(1) 阅读此算法，说明它的功能。
6
(2) 对于下面给出的整数数组，追踪第一趟while ( d > 0 ) 内的每次for循环结束时数组中数据的变化。（为清楚起见，本次循环未涉及的不移动的数据可以不写出，每行仅写出一个for循环的变化） (3) 以上各次循环的数据移动次数分别是多少。
五、算法分析题（每小题5分，共15分） (1) 希尔排序
(2) 第一趟while循环内各for循环结束时数组中数据的变化： 步 1 2 3 4 5 6 a[0] 77 33 a[1] 44 44 11 a[2] 99 88 a[3] 66 22 a[4] 33 77 44 a[5] 55 55 44 a[6] 88 99 a[7] 22 66 a[8] 44 77 a[9] 11 55 移动次数 3 2 3 3 3 4 (3) 各趟数据移动次数见表的最右一栏。
六、算法设计题（每小题5分，共15分）
下面是队列和栈的类声明：
template
queue ( );
//队列的构造函数 //队列的复制构造函数 //赋值操作
//判断队列空否，=1为空, =0不空 //返回队头元素的值 //将新元素插入到队列的队尾 //从队列的队头删除元素 //其他成员函数
queue (const queue& qu); bool isEmpty ( ); Type& getFront ( ); void pop ( ); //……
queue& operator= (const queue& qu);
void push (const Type& item);
}
template
7
public: }
stack ( );
//栈的构造函数
//判断栈空否。=1栈空，=0不空 //将新元素进栈 //栈顶元素退栈 //返回栈顶元素的值
bool isEmpty ( ); void pop ( );
void push ( const stack& item ); Type& getTop ( );
试利用栈和队列的成员函数，编写以下针对队列的函数的实现代码（要求非递归实现）。
(1) “逆转”函数 template
六、算法设计题（每小题5分，共15分）
(1) #include “stack”
template
void reverse (queue
};
}
8
(2) “判等”函数 bool queue::operator== (const queue& Q);（5分） (3) “清空”函数 void queue::clear ( ); （5分）
//普通函数
stack
{ tmp = Q.getFront(); Q.Pop(); S.Push (tmp); } while ( !S.isEmpty() )
//成员函数
queue
t1 = getFront(); Pop(); Q1.Push(t1); if ( t1 != t2 ) { finished = false; break; }
//从左队列退出, 进临时队列
t2 = Q.getFront(); Q.Pop(); Q2.Push(t2); //从右队列退出, 进临时队列 { tmp = S.getTop(); S.Pop(); Q.EnQueue(); }
(2) bool queue::operator== (const queue& Q) {
while ( !Q1.isEmpty() ) { t1 = Q1.getFront(); Q1.Pop(); Push(t1); } while ( !Q.isEmpty() ) { t2 = Q.getFront(); Q.Pop(); Q2.Push(t2); } while ( !Q2.isEmpty() ) { t2 = Q2.getFront(); Q2.Pop(); Q.Push(t2); }
(3) void queue::clear ( ) {
};
//成员函数
while ( !isEmpty() ) Pop();
9