数据结构20250620_数据结构考试

试卷01

天津金海通软件笔试题

• 选择题(4*4=16)

1. 对于双向循环链表,在p指针所指的结点之后插入s指针所指结点的操作应为

1. p->next=s;  s->pri=p;  p->next->pri=s;  s->next=p->next
2. p->next=s;  p->next->pri=s;  s->pri=p;  s->next=p->next
3. s->pri =p;  s->next=p->next;  p->next=s;  p->next->pri=s
4. s->pri=p;  s->next=p->next;  p->next->pri=s;  p->next=s;

1. 以下程序的输出结果是（  ）

void main()

{

char st[20] = “hello\0\t\\\”;

printf(“%d %d \n”, strlen(st), sizeof(st));

return;

}

        A.9 9 B．5 20 C．13 20 D．20 20

1. 若入栈序列的元素顺序为A,B,C,D,E,判断下列哪一个出栈序列是不可能的。

1. A、B、C、D、E
2. B、C、D、E、A
3. E、A、B、C、D
4. D、C、B、A、E

1. 将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度采用大O形式表示应该是（）

1. O(1)
2. O(n)
3. O(m)
4. O(n+m)

二、填空题(5*3+6=21)

1. 有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当折半查找值为82的结点时，__________4_____________________次比较后查找成功。
2. 用P表示入栈操作，D表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的P和D的操作串为_________________PDPPDPDD__________________________
3. 头文件中的 ifndef/define/endif 干什么用____防止头文件的重复包含______
4. Makefile根据文件的___________时间戳___________判断文件是否需要重新编译
5. 折半查找的前提条件____________________序列有序_______________
6. 假设以数组seqn[m]存放循环队列的元素,设变量rear和front分别指示循环队列中队尾的位置和队头的位置。(6)
   1. 如何判断队列为空、已满
   2. 如果计算队列中元素的个数

• 简答题(4*5=20)

1. 写出下列序列一次快速排序的结果：[3, 1, 4, 1, 5, 9, 2, 6]
2. 思考如何用两个栈实现一个队列，简述思路即可
3. 已知一棵二叉树的先序和中序遍历序列：先序:A、B、C、D、E、F、G、H、I、J中序:C、B、A、E、F、D、I、H、J、G画出该二叉树
4. 简述make工具的使用方式

四、编程题（43）

1. 有如下定义的

struct Node{

int Value; //该 node 的值

struct Node * Next；//指向下一个 Node

}

请写一个函数，能够将输入的 Struct node 插入已有链表的末尾（7）

Void InserNode(struct Node* pList, struct Node* pInsertNode)

{}

1. 写出折半查找的代码（8）
2. 现已知单链表的头结点struct node *H; 写一个代码将单向链表逆置（10）
   1. 将原来的第一个结点变成最后一个结点
   2. 保存原来的第二个结点
   3. 循环头插(还需要再有一个指针保存下一个要头插结点的地址)
3. 实现顺序栈的结构体、创建、入栈的代码（7）
4. 现在有一个简单的工程项目，由main.c fun.c fun1.c和fun.h四个文件组成(且当前目录下只有这四个文件)。其main.c中包含主函数和fun.h的头文件，fun.c和fun1.c中为功能函数的实现，fun.h中为fun.c和fun1.c中功能函数的声明 。请写一个Makefile实现这几个文件的编译，提示Makefile提供的自动变量：$@所有目标、$^所有依赖、$<第一个依赖（11）
   
   
   

试卷02

蓝际网络笔试题

一、选择题（4*5=20)
1.下列关于存储结构和逻辑结构描述正确的是（  )
 a)存储结构和程序具体实现的语言没有关系
 b)算法的实现需要考虑逻辑结构
 c)逻辑结构就是实际的存储结构
 d)算法的实现依赖于存储结构
2.一个栈的入栈序列是 a , b , c , d , e ，则栈的不可能的输出序列是（  )
 a ) edcba 
 b ) decba 
 c ) dceab 
 d ) abcde 
3.一个算法的时间复杂度为 T ( n )=2n^3+3n^2+4n+5log2n+2，则该 T ( n ）应记为
(  )
 a ) O ( n )
 b ) O ( n ^3)
 c ) O ( n ^4)
 d ) O (log2n)
4.在一个完全二叉树中，编号为 i 的节点存在左孩子，则左孩子的编号是，设根节点编号为0(   )
 a )2i
 b )2i-1
 c )2i+1
 d )2i+2
5.在链表指针为 p 的结点之后插入指针为 s 的结点，正确的操作是哪一项？(   )
 a ) p.next = s ; s.next = p.next ;

 b ) s.next = p.next ; p.next = s ;

 c ) p.next = s ; p.next = s.next ;

 d ) p.next = s.next ; p.next = s ;
二、简答题（40)
1.画二叉树写出先序遍历，后序： DBAEGHFIC 中序： DEBACGFHI (10)
2.算法的设计要求（5）
3.求下列结构体的大小，写出求解过程（默认64位操作系统对齐）(10)

typedef struct{
    char name[20];
    struct
    {
        int day;
        char sex;
        short year;
    }p1;
    struct
    {
        short month;
        long num;
    }p2;
}LibraryRecord;

4.用两个栈实现一个队列的功能？简述算法和思路（10)

5.求下列共用体的大小（默认64位操作系统）(5)
 

UnionA
{
    int arr[5];
    long int a;
};

三、编程题（40)
1.写出程序删除单链表中的所有节点（10)
2.写程序，双向循环链表的结构体，及其头节点的创建和任意位置插入函数。(10)

3.折半查找的前提条件是什么？写出折半查找的代码（10)
4.写出一个循环队列的结构体，该队列元素最多是 m 个。(10)
 a )写出如何判断该队列为空的函数
 b )写出如何判断该队列为满的函数
 c )写出计算当前队列中的元素个数的函数