当前位置：文档之家› 上海交通大学试卷A卷NO

上海交通大学试卷A卷NO

班级姓名学号分数

一、编程序题（本大题共计二小题，共计40 分，第1题25 分，第2题15分。）

1、设在二叉排序树的每个结点中，含类型为Type 的数据场data 域。当向该二叉排

序树中插入一个数据值为key 的新结点时，若二叉排序树中已存在数据值为key的结点，则插入失败，并返回0；否则就创建一个数据值为key的结点，然后将其插入到该二叉排序树中并仍满足二叉排序树的性质，且返回1。按照这种插入要求，请编写一个二叉排序树的成员函数Insert_key(const Type & key，BSTNode * T ))。注意本函数使用的额外空间只能为O（1），这也意味做不可使用递归。

该二叉排序树的结点定义如下：

template

struct BSTNode { // 二叉排序树的结点的表示。

Type data; // 结点的数据值。

BSTNode * left; // 给出结点的左儿子的地址。

BSTNode * right; // 给出结点的右儿子的地址。

BSTNode ( ): left(NULL), right(NULL) { }

~BSTNode( ) { }

};

二叉排序树类BinarySearchTree的定义如下：

template

class BinarySearchTree{

public:

BinarySearchTree ( ) : Root(NULL) { }

~BinarySearchTree ( ) { }

int Insert_key (const Type & key ) { return Insert_key ( key，Root ); }

……

protected:

BSTNode * Root; // 二叉排序树的根结点的地址。

int Insert_key (const Type & key，BSTNode * T );

……

};

班级姓名学号请在此书写第1小题的答案：

班级姓名学号

2. 已知单链表类及其单链表结点类的定义如下：

template < class ElemType> class List; // 单链表类的向前说明。

template < class ElemType> class ListNode{ // 结点类

friend class List ;

// 单链表类为其友元类, 便于访问结点类中的私有成员。

public:

ListNode( ):Next(NULL){ }

~ListNode( ) { }

private:

ListNode * Next; // 给出本结点的下一结点的地址。

ElemType Element; // 结点数据场。

};

template class List{ // 单链表类。

private:

ListNode * head;

// head为指向头结点的指针，头结点的指针场给出该链表中的第一个结点的地址。

public:

List( ) { head = new ListNode< ElemType >( ); }

~ List( ) { MakeEmpty( ); delete head; } // 析构函数：将单链表清空,具体实现略。

int Count ( );

// 该函数统计单链表中的(不含头结点)结点总数。若表空，则返回0；否则

// 返回该单链表的结点总数。

。。。。。。

};

请编程实现单链表类的成员函数int Count ( )；其功能见该函数的注解行。注意：所使用的额外空间只能为O(1)，否则不得分。

班级姓名学号请在此书写第2小题的答案：

班级姓名学号

二、回答题（本题共3 题，共计25 分，1、3题7分，2 题11分）

1、请问：层数总数为L的完全二叉树的结点总数，最多为多少？最少为多少？为什

么？

2、对二叉树中结点进行按层次顺序的访问操作（从根结点开始，自上而下进行访问，每一层结点的访问顺序为自左至右）称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。已知一棵二叉树的层次序列为A、B、C、D、E、F、G、H、I、J，中序序列为D、B、G、E、H、J、A、C、I、F，请画出该二叉树。

3、快速排序法和堆排序法，是二种常用的排序法。在平均情况下和最坏情况下，它们的时间复杂性级别分别为多少？它们所使用的额外空间的空间复杂性的级别呢？

班级姓名学号

三、填充题和选择题（本大题共 5 小题，每小题7 分）

1、设有如下的时间复杂性级别，请按级别从低到高的顺序排成一行。

O（3n

）、O（2

）、O（1）、O（n

1/2

）、O（log2n）、O（n

）、O（n

）、

答：

2、在一个单链表中，若要删除指针q所指结点的直接后继结点，则执行( )。注：next 指针场给出本结点的直接后继结点的地址。

A．p = q->next; q->next = p->next；delete p;

B．q->next＝q->next；p＝q->next；delete p;

C．q->next＝q->next->next; p = q->next; delete p;

3、在一个双链表中，若要删除指针q所指的结点，则执行( )。注：prior和next 指针场给出本结点的直接前驱结点和直接后继结点的地址。

A．q->prior->next = q->next; q->next->prior = p->prior；delete q;

B．q->prior->next = q->next; delete q; q->next->prior = p->prior；

C．q->next->prior = p->prior；delete q; q->prior->next = q->next;

4、在有序表中，应用折半查找法成功地找到一个结点，在平均情况下的时间复杂性是[ ], 在最坏情况下的时间复杂性是[ ]。设结点个数为n，以大O形式给出时间复杂性。

5、在平衡二叉排序树上成功地找到一个结点，在平均情况下的时间复杂性是 [ ], 在最坏情况下的时间复杂性是 [ ]。设结点个数为 n，以大O形式给出时间复杂性

上海交通大学试卷( A 卷)

上海交通大学试卷（ A 卷）课程线性代数（B 类）学期 2011－2012第1学期班级号学号姓名一．单项选择题（每题3分，共18分） 1．设A ，B 为n 阶方阵，且A A =2 ，B B =2 。则（）（A ）)()(B r A r =时，A ，B 不相似；（B ）)()(B r A r ≠时，A ，B 相似；（C ）)()(B r A r =时，A ，B 相似；（D ）以上都有可能。 2．设A 为n 阶反对称矩阵，则（）（A ）0)(=+E A r ；（B ）n E A r =+)(；（C ）n E A r <+<)(0；（D ）以上都有可能。 3．设B A ,为n 阶方阵，??? ? ??=B A C 00。则伴随矩阵* C 为（）（A ）???? ??** B A A B ||0 0||；（B ）??? ? ??**B B A A ||00||；（C ）???? ? ?** A A B B ||0 0||；（D ）??? ? ? ?**A B B A ||00||。 4．设A 为n m ?的实矩阵，矩阵)(A A T 正定的充分必要条件为（）（A ）m A r =)(；（B ）m A r <)(；（C ）m A r <)(；（D ）n A r =)(。 5．设α是单位向量，矩阵ααT k E A +=，其中1-≠k 。则（）我承诺，我将严格遵守考试纪律。

（A ）A 为正交矩阵；（B ）A 为正定矩阵；（C ）A 为可逆矩阵；（D ）A 为反对称矩阵。 6．设向量组321,,ααα线性无关，向量321,,βββ线性相关但相互不成比例，且， 321332123211,,αααβαααβαααβk k k ++=++=++=。则（）（A ）2-=k 或 1=k ；（B ）1=k ；（C ）2-≠k 且 1≠k ；（D ）2-=k 。二．填空题（每题3分，共18分） 7．设行列式 4 111311 12=D ，j i A 是D 中元素j i a 的代数余子式，则 ∑∑==313 1 i j j i A ＝。 8．已知4阶行列式4||j i a 的展开式中某项为42143123)1(a a a a k -。则=k 。 9. 设33)(?=ij a A ,j i A 是||A 中j i a 的代数余子式，j i j i A a =，13 121132a a a ==。已知011