После функции mysql_connect добавьте строку:
mysql_query('SET NAMES cp1251');

config_db.php
<?
$host="localhost";
$user="root";
$pass="1234";

$link=mysql_connect($host, $user, $pass) // Соединение с MySQL
   or die ("Невозможно подключиться к MySQL");
   
$bd_name="test"; // Имя созданной базы данных

if (mysql_select_db($bd_name)) // Выбор базы данных
{
    echo "Подключены к базе данных ".$bd_name;
}
   else echo ("Невозможно выбрать БД");
?>

cr_db_table.php
<?php
include "config_db.php";

$table_name="cat"; // Имя создаваемой таблицы 

$table="CREATE TABLE ".$table_name." (num int(10) NOT NULL auto_increment, name text, PRIMARY KEY (num)) TYPE=MyISAM";

if (mysql_query($table)) // Отсылаем запрос на создание таблицы
{echo "<br />Таблица создана";} 
else echo ("<br />Невозможно создать таблицу"); 

mysql_close($link); // Разрываем соединение с MySQL
?>

add_data_cat.php
<?php
include "config_db.php";

$query="INSERT INTO cat VALUES (3, `frrr`)";

if (mysql_query($query, $link))
{echo "<br />good";}
else {echo "<br />bad";}

mysql_close($link); // Разрываем соединение с MySQL
?>

Попробуйте в phpMyAdmin этот запрос выполнить.
Если не сможете разобраться, то покажите весь код вместе с запросом.